Primal beats dual on online packing LPs in the random-order model
DOI10.1137/15M1033708zbMATH Open1411.90216OpenAlexW2899383020WikidataQ129020078 ScholiaQ129020078MaRDI QIDQ4554073FDOQ4554073
Authors: Thomas Kesselheim, Klaus Radke, Andreas Tönnis, Berthold Vöcking 
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
Recommendations
Online algorithms; streaming algorithms (68W27) Analysis of algorithms and problem complexity (68Q25) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08)
Cites Work
- Online primal-dual algorithms for covering and packing
- AdWords and generalized online matching
- Title not available (Why is that?)
- A Knapsack Secretary Problem with Applications
- A multiple-choice secretary algorithm with applications to online auctions
- A dynamic near-optimal algorithm for online linear programming
- Title not available (Why is that?)
- Online stochastic packing applied to display ad allocation
- Fast algorithms for online stochastic convex programming
- Online bipartite matching with unknown distributions
- Online bipartite matching with random arrivals, an approach based on strongly factor-revealing LPs
- Algorithms for Secretary Problems on Graphs and Hypergraphs
- Dynamic Programming and Decision Theory
- Randomized Distributed Edge Coloring via an Extension of the Chernoff--Hoeffding Bounds
- Truthful and Near-Optimal Mechanism Design via Linear Programming
- Approximability of sparse integer programs
- An optimal online algorithm for weighted bipartite matching and extensions to combinatorial auctions
- Secretary Problems with Non-Uniform Arrival Order
- Solving packing integer programs via randomized rounding with alterations
Cited In (14)
- Improved Online Algorithms for Knapsack and GAP in the Random Order Model
- New bounds for online packing LPs
- Primal beats dual on online packing LPs in the random-order model
- Online lower bounds via duality
- Improved online algorithms for knapsack and GAP in the random order model
- Monotone \(k\)-submodular secretary problems: cardinality and knapsack constraints
- Online stochastic packing applied to display ad allocation
- A dynamic near-optimal algorithm for online linear programming
- Packing returning secretaries
- Knapsack secretary through boosting
- Online generalized assignment problem with historical information
- Machine covering in the random-order model
- Near optimal online algorithms and fast approximation algorithms for resource allocation problems
- A truthful near-optimal mechanism for online linear packing-covering problem in the random order model
This page was built for publication: Primal beats dual on online packing LPs in the random-order model
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4554073)
