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
- 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
- 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?)
- 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
(24)- Improved bounds for randomized preemptive online matching
- Buyback problem with discrete concave valuation functions
- Structural results on matching estimation with applications to streaming
- Online budgeted maximum coverage
- Unit cost buyback problem
- Maximum matching on trees in the online preemptive and the incremental graph models
- Proportional cost buyback problem with weight bounds
- Buyback problem with discrete concave valuation functions
- Clairvoyant mechanisms for online auctions
- Unit cost buyback problem
- Streaming algorithms for submodular function maximization
- On randomized algorithms for matching in the online preemptive model
- The power of deferral: maintaining a constant-competitive Steiner tree online
- Online unweighted knapsack problem with removal cost
- Online submodular maximization with preemption
- Online maximum matching with recourse
- The power of subsampling in submodular maximization
- Proportional Cost Buyback Problem with Weight Bounds
- Small Space Stream Summary for Matroid Center
- Online algorithm for fractional matchings with edge arrivals in graphs of maximum degree three
- Deletion robust non-monotone submodular maximization over matroids
- Online stochastic matching with edge arrivals
- Edge arrival online matching: the power of free disposal on acyclic graphs
- Online maximum matching with recourse
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)
