Lattice approximation and linear discrepency of totally unimodular matrices
Lattice approximation and linear discrepency of totally unimodular matrices
复制标题
全幺模矩阵的格逼近和线性差异
DOI：
--
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
Benjamin Doerr
中科院分区：
文献类型：
--
作者：
Benjamin Doerr
本文证明了完全单模矩阵<i>A</i>∈R<sup><i>m</i> x <i>n</i></sup>的格逼近问题可以通过线性规划方法有效且最优地求解。本算法的复杂度为<i>&Ogr；</i>(log <i>m</i>)乘以用2个（<i>m</i> + <i>n</i>）线性约束描述的R<sup>n</sup>中找到多极体极值点的复杂度。
This paper shows that the lattice approximation problem for totally unimodular matrices <i>A</i> ∈ R<sup><i>m</i>×<i>n</i></sup> can be solved efficiently and optimally via a linear programming approach. The complexity of our algorithm is <i>&Ogr;</i>(log <i>m</i>) times the complexity of finding an extremal point of a polytope in R<sup>n</sup> described by 2(<i>m</i> + <i>n</i>) linear constraints.
We also consider the worst-case approximability. This quantity is usually called linear discrepancy lindisc(<i>A</i>). For any totally unimodular <i>m</i> × <i>n</i> matrix <i>A</i> we show lindisc(<i>A</i>) ≤ min{1 - 1/<i>n</i>+1, 1 - 1/<i>m</i>}.
This bound is sharp. It proves Spencer's conjecture lindisc(<i>A</i>) ≤ (1 - 1/<i>n</i>+1) herdisc(<i>A</i>) for totally unimodular matrices. This seems to be the first time that linear programming is successfully used for a discrepancy problem.