Computer Science – Data Structures and Algorithms
Scientific paper
2012-04-26
Computer Science
Data Structures and Algorithms
Scientific paper
We consider packing LP's with $m$ 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.
Molinaro Marco
Ravi R.
No associations
LandOfFree
Geometry of Online Packing Linear Programs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Geometry of Online Packing Linear Programs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Geometry of Online Packing Linear Programs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-313559