Geometry of online packing linear programs
From MaRDI portal
Publication:2843293
DOI10.1007/978-3-642-31594-7_59zbMATH Open1272.68473arXiv1204.5810OpenAlexW2112788936MaRDI QIDQ2843293FDOQ2843293
Authors: Marco Molinaro, R. Ravi 
Publication date: 12 August 2013
Published in: Mathematics of Operations Research, Automata, Languages, and Programming (Search for Journal in Brave)
Abstract: We consider packing LP's with rows where all constraint coefficients are normalized to be in the unit interval. The n columns arrive in random order and the goal is to set the corresponding decision variables irrevocably when they arrive so as to obtain a feasible solution maximizing the expected reward. Previous (1 - epsilon)-competitive algorithms require the right-hand side of the LP to be Omega((m/epsilon^2) log (n/epsilon)), a bound that worsens with the number of columns and rows. However, the dependence on the number of columns is not required in the single-row case and known lower bounds for the general case are also independent of n. Our goal is to understand whether the dependence on n is required in the multi-row case, making it fundamentally harder than the single-row version. We refute this by exhibiting an algorithm which is (1 - epsilon)-competitive as long as the right-hand sides are Omega((m^2/epsilon^2) log (m/epsilon)). Our techniques refine previous PAC-learning based approaches which interpret the online decisions as linear classifications of the columns based on sampled dual prices. The key ingredient of our improvement comes from a non-standard covering argument together with the realization that only when the columns of the LP belong to few 1-d subspaces we can obtain small such covers; bounding the size of the cover constructed also relies on the geometry of linear classifiers. General packing LP's are handled by perturbing the input columns, which can be seen as making the learning problem more robust.
Full work available at URL: https://arxiv.org/abs/1204.5810
Recommendations
Online algorithms; streaming algorithms (68W27) Linear programming (90C05) Randomized algorithms (68W20)
Cited In (25)
- Improved Online Algorithms for Knapsack and GAP in the Random Order Model
- Title not available (Why is that?)
- Title not available (Why is that?)
- Secretary markets with local information
- Simple and fast algorithm for binary integer and online linear programming
- Online Appointment Scheduling in the Random Order Model
- Online Submodular Maximization Problem with Vector Packing Constraint.
- Improved online algorithms for Knapsack and GAP in the random order model
- A dynamic learning algorithm for online matching problems with concave returns
- Competitive online algorithms for resource allocation over the positive semidefinite cone
- Secretary Markets with Local Information
- An Approximation Algorithm for Network Revenue Management Under Nonstationary Arrivals
- Title not available (Why is that?)
- Online Linear Programming: Dual Convergence, New Algorithms, and Regret Bounds
- Packing returning secretaries
- A stochastic algorithm for online bipartite resource allocation problems
- Online generalized assignment problem with historical information
- Iterative computation of security strategies of matrix games with growing action set
- How the experts algorithm can help solve LPs online
- Primal Beats Dual on Online Packing LPs in the Random-Order Model
- Online Submodular Welfare Maximization: Greedy Beats 1/2 in Random Order
- A Dynamic Near-Optimal Algorithm for Online Linear Programming
- Submodular Secretary Problems: Cardinality, Matching, and Linear Constraints
- A truthful near-optimal mechanism for online linear packing-covering problem in the random order model
- Adversarial bandits with knapsacks
This page was built for publication: Geometry of online packing linear programs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2843293)
