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.
author:
- |
    Marco Molinaro\
    Carnegie Mellon
- |
    R. Ravi\
    Carnegie Mellon
bibliography:
- 'online-lp.bib'
title: Geometry of Online Packing Linear Programs
---

Introduction
============

Traditional optimization models usually assume that the input is known a priori. However, in most applications, the data is either revealed over time or only coarse information about the input is known, often modeled in terms of a probability distribution. Consequently, much effort has been directed towards understanding the quality of solutions that can be obtained without full knowledge of the input, which led to the development of online and stochastic optimization [@borodinbook; @stocprogbook]. Emerging problems such as allocating advertisement slots to advertisers and yield management in the internet are of inherent online nature and have further accelerated this development [@agrawal].

Linear programming is arguably the most important and thus well-studied optimization problem. Therefore, understanding the limitations of solving linear programs when 