Primal Beats Dual on Online Packing LPs in the Random-Order Model
From MaRDI portal
Publication:4554073
DOI10.1137/15M1033708zbMath1411.90216WikidataQ129020078 ScholiaQ129020078MaRDI QIDQ4554073
Thomas Kesselheim, Klaus Radke, Berthold Vöcking, Andreas Tönnis
Publication date: 7 November 2018
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/15m1033708
68Q25: Analysis of algorithms and problem complexity
90C08: Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.)
68W27: Online algorithms; streaming algorithms
Related Items
Improved Online Algorithms for Knapsack and GAP in the Random Order Model, Packing returning secretaries, Machine covering in the random-order model, Knapsack secretary through boosting, Improved online algorithms for Knapsack and GAP in the random order model, Online generalized assignment problem with historical information, Monotone \(k\)-submodular secretary problems: cardinality and knapsack constraints
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Approximability of sparse integer programs
- How the Experts Algorithm Can Help Solve LPs Online
- Geometry of Online Packing Linear Programs
- An Optimal Online Algorithm for Weighted Bipartite Matching and Extensions to Combinatorial Auctions
- A Dynamic Near-Optimal Algorithm for Online Linear Programming
- Secretary Problems with Non-Uniform Arrival Order
- Online Primal-Dual Algorithms for Covering and Packing
- AdWords and generalized online matching
- Online Stochastic Packing Applied to Display Ad Allocation
- A Knapsack Secretary Problem with Applications
- Randomized Distributed Edge Coloring via an Extension of the Chernoff--Hoeffding Bounds
- Algorithms for Secretary Problems on Graphs and Hypergraphs
- Fast Algorithms for Online Stochastic Convex Programming
- Truthful and Near-Optimal Mechanism Design via Linear Programming
- Online bipartite matching with unknown distributions
- Online bipartite matching with random arrivals
- Dynamic Programming and Decision Theory
