Buyback problem -- approximate matroid intersection with cancellation costs
From MaRDI portal
Abstract: In the buyback problem, an algorithm observes a sequence of bids and must decide whether to accept each bid at the moment it arrives, subject to some constraints on the set of accepted bids. Decisions to reject bids are irrevocable, whereas decisions to accept bids may be canceled at a cost that is a fixed fraction of the bid value. Previous to our work, deterministic and randomized algorithms were known when the constraint is a matroid constraint. We extend this and give a deterministic algorithm for the case when the constraint is an intersection of matroid constraints. We further prove a matching lower bound on the competitive ratio for this problem and extend our results to arbitrary downward closed set systems. This problem has applications to banner advertisement, semi-streaming, routing, load balancing and other problems where preemption or cancellation of previous allocations is allowed.
Recommendations
Cites work
- scientific article; zbMATH DE number 3544074 (Why is no real title available?)
- scientific article; zbMATH DE number 3635849 (Why is no real title available?)
- scientific article; zbMATH DE number 1263237 (Why is no real title available?)
- scientific article; zbMATH DE number 1305386 (Why is no real title available?)
- A Knapsack Secretary Problem with Applications
- A multiple-choice secretary algorithm with applications to online auctions
- Algorithms for Secretary Problems on Graphs and Hypergraphs
- An Analysis of the Greedy Heuristic for Independence Systems
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- Combining online algorithms for acceptance and rejection
- Efficient On-Line Call Control Algorithms
- Estimating PageRank on graph streams
- Graph distances in the streaming model: the value of space
- IMPROVED APPROXIMATION GUARANTEES FOR WEIGHTED MATCHING IN THE SEMI-STREAMING MODEL *
- Matroids, secretary problems, and online mechanisms
- Multi-parameter mechanism design and sequential posted pricing
- Non-monotone submodular maximization under matroid and knapsack constraints
- On graph problems in a semi-streaming model
- Positivity of second order linear recurrent sequences
- Trading off space for passes in graph streaming problems
Cited in
(23)- Deletion robust non-monotone submodular maximization over matroids
- Unit cost buyback problem
- Online maximum matching with recourse
- Online maximum matching with recourse
- Improved bounds for randomized preemptive online matching
- Buyback problem with discrete concave valuation functions
- Structural results on matching estimation with applications to streaming
- The power of deferral: maintaining a constant-competitive Steiner tree online
- Small Space Stream Summary for Matroid Center
- On randomized algorithms for matching in the online preemptive model
- Maximum matching on trees in the online preemptive and the incremental graph models
- Unit cost buyback problem
- Clairvoyant mechanisms for online auctions
- Online stochastic matching with edge arrivals
- Online algorithm for fractional matchings with edge arrivals in graphs of maximum degree three
- Proportional Cost Buyback Problem with Weight Bounds
- Online unweighted knapsack problem with removal cost
- The power of subsampling in submodular maximization
- Streaming algorithms for submodular function maximization
- Buyback problem with discrete concave valuation functions
- Online submodular maximization with preemption
- Online budgeted maximum coverage
- Proportional cost buyback problem with weight bounds
This page was built for publication: Buyback problem -- approximate matroid intersection with cancellation costs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3012820)
