Buyback Problem - Approximate Matroid Intersection with Cancellation Costs

DOI10.1007/978-3-642-22006-7_32zbMath1333.91014arXiv1009.5037OpenAlexW3098705741MaRDI QIDQ3012820

Ashwinkumar Badanidiyuru Varadaraja

Publication date: 6 July 2011

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1009.5037

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Auctions, bargaining, bidding and selling, and other market models (91B26) Combinatorial aspects of matroids and geometric lattices (05B35)

Related Items (19)

Online maximum matching with recourse ⋮ 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 ⋮ The Power of Subsampling in Submodular Maximization ⋮ Submodular maximization meets streaming: matchings, matroids, and more ⋮ Proportional cost buyback problem with weight bounds ⋮ Improved bounds for randomized preemptive online matching ⋮ Online unweighted knapsack problem with removal cost ⋮ Small Space Stream Summary for Matroid Center ⋮ Online Maximum Matching with Recourse ⋮ Online budgeted maximum coverage ⋮ Buyback problem with discrete concave valuation functions ⋮ Structural results on matching estimation with applications to streaming ⋮ Proportional Cost Buyback Problem with Weight Bounds ⋮ Clairvoyant Mechanisms for Online Auctions ⋮ Online Submodular Maximization with Preemption ⋮ Unit cost buyback problem ⋮ Maximum matching on trees in the online preemptive and the incremental graph models

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Positivity of second order linear recurrent sequences
• On graph problems in a semi-streaming model
• Multi-parameter mechanism design and sequential posted pricing
• Estimating PageRank on graph streams
• IMPROVED APPROXIMATION GUARANTEES FOR WEIGHTED MATCHING IN THE SEMI-STREAMING MODEL *
• Efficient On-Line Call Control Algorithms
• A Knapsack Secretary Problem with Applications
• An Analysis of the Greedy Heuristic for Independence Systems
• Non-monotone submodular maximization under matroid and knapsack constraints
• Algorithms for Secretary Problems on Graphs and Hypergraphs
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Trading off space for passes in graph streaming problems

This page was built for publication: Buyback Problem - Approximate Matroid Intersection with Cancellation Costs