Geometry of Online Packing Linear Programs
Geometry of Online Packing Linear Programs
复制标题
DOI：
10.1007/978-3-642-31594-7_59
复制
发表时间：
2012-04
期刊：
影响因子：
--
通讯作者：
Marco Molinaro Carnegie;Mellon R. Ravi;C. Mellon
中科院分区：
文献类型：
--
作者：
Marco Molinaro Carnegie;Mellon R. Ravi;C. Mellon
考虑线性规划的mrows包装，其中所有的约束系数被归一化为在单位区间。然后，列以随机顺序到达，目标是在它们到达时合理地设置相应的决策变量，以获得最大化期望回报的可行解。以前的（1 −ε）-竞争算法要求线性规划的右侧为Ω（（m/ε2）log（n/ε）），这是一个与列数和行数相关的界限。然而，在单行的情况下，列数的依赖是不需要的，已知的一般情况下的下限也是独立的n。我们的目标是了解是否依赖onnis需要在多行的情况下，使它从根本上比单行版本。我们通过展示一个算法来反驳这一点，只要右边是Ω（（m2/ε2）log（m/ε）），这个算法就是（1 −ε）-竞争的。我们的技术完善以前可能近似正确的学习为基础的方法，解释在线决策的线性分类的列的基础上采样的双重价格。我们的改进的关键成分来自于一个非标准的覆盖参数，以及只有当线性规划的列属于几个一维子空间时，我们才能获得这样小的覆盖;构建的覆盖大小的边界也依赖于线性分类器的几何形状。一般的填充线性规划是通过扰动输入列来处理的，这可以被看作是使学习问题更加鲁棒。
We consider packing linear programs withmrows where all constraint coefficients are normalized to be in the unit interval. Thencolumns arrive in random order and the goal is to set the corresponding decision variables irrevocably when they arrive to obtain a feasible solution maximizing the expected reward. Previous (1 −ε)-competitive algorithms require the right-hand side of the linear program to be Ω((m/ε2)log(n/ε)), 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 ofn.Our goal is to understand whether the dependence onnis required in the multirow case, making it fundamentally harder than the single-row version. We refute this by exhibiting an algorithm that is (1 −ε)-competitive as long as the right-hand sides are Ω((m2/ε2)log(m/ε)). Our techniques refine previous probably approximately correct learning based approaches that interpret the online decisions as linear classifications of the columns based on sampled dual prices. The key ingredient of our improvement comes from a nonstandard covering argument together with the realization that only when the columns of the linear program belong to few one-dimensional subspaces we can obtain such small covers; bounding the size of the cover constructed also relies on the geometry of linear classifiers. General packing linear programs are handled by perturbing the input columns, which can be seen as making the learning problem more robust.