arXiv preprint ·
Large-Scale Trade-Off Curve Computation for Incentive Allocation with Cardinality and Matroid Constraints
- Published
- Source
- arXiv preprint, posted before peer review
- DOI
- 10.24963/ijcai.2025/287
- Original
- Read it at arXiv
- Topics
Abstract
We consider a large-scale incentive allocation problem where the entire trade-off curve between budget and profit has to be maintained approximately at all times. The application originally comes from assigning coupons to users of ride-sharing apps, where each user can have a limit on the number of coupons assigned to them. We consider a more general form, where the coupons for each user form a matroid, and the set of coupons assigned to each user must be an independent set. We show the entire trade-off curve can be maintained approximately in near real time.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Spectral Gap of Down-Up Walks via Trickle-Down: A Simplified and Sharpened Analysis
Succinct Representation of Search Trees on Trees
Universal set families for maximization of nonnegative submodular and XOS functions
The Complexity of Computing Class Probabilities in BID Probabilistic Databases
A $(1+1/\sqrt{2})$-Approximation for the Multiple-Depot Traveling Salesman Problem
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.