论文标题
关于线性差异的计算复杂性
On the Computational Complexity of Linear Discrepancy
论文作者
论文摘要
计算机科学和应用数学方面的许多问题都需要将分数值的矢量$ \ mathbf {w} $置于间隔$ [0,1] $上的分数值$ \ Mathbf {x} $ $ \ mathbf {a} \ mathbf {w} $。例如，在LP圆形算法中出现此问题，用于近似于$ \ Mathsf {np} $ - 硬优化问题以及用于数值集成的均匀分布点集的设计。对于给定的矩阵$ \ mathbf {a} $，与最佳可能的$ \ mathbf {w} $的所有选择相比，最坏的错误是由最佳可能的舍入所产生的，这是通过$ \ m m mathbf {a a} $的线性不计量来衡量的，在差异理论中所研究的数量是由lovasz，spencz，spenceg ofs comb，ej comb，ej comb，ej comb＆diste comb，comb＆vesti comb＆vesti comb＆vers comb＆vers c。 我们开始研究线性差异的计算复杂性。我们的调查沿两个方向进行：（1）证明硬度结果，（2）找到精确和近似算法来评估某些矩阵的线性不相差。对于（1），我们表明线性差异为$ \ mathsf {np} $ - 硬。因此，我们不希望为总体情况找到有效的精确算法。将我们的注意力限制为具有恒定行数的矩阵，我们为由单行和矩阵组成的矩阵提出了一个poly-time精确算法，该矩阵具有恒定数量的行和边界幅度的条目。我们还提出了一种通用矩阵的指数时间近似算法，以及一种近似线性差异与指数因子内的算法。
Many problems in computer science and applied mathematics require rounding a vector $\mathbf{w}$ of fractional values lying in the interval $[0,1]$ to a binary vector $\mathbf{x}$ so that, for a given matrix $\mathbf{A}$, $\mathbf{A}\mathbf{x}$ is as close to $\mathbf{A}\mathbf{w}$ as possible. For example, this problem arises in LP rounding algorithms used to approximate $\mathsf{NP}$-hard optimization problems and in the design of uniformly distributed point sets for numerical integration. For a given matrix $\mathbf{A}$, the worst-case error over all choices of $\mathbf{w}$ incurred by the best possible rounding is measured by the linear discrepancy of $\mathbf{A}$, a quantity studied in discrepancy theory, and introduced by Lovasz, Spencer, and Vesztergombi (EJC, 1986). We initiate the study of the computational complexity of linear discrepancy. Our investigation proceeds in two directions: (1) proving hardness results and (2) finding both exact and approximate algorithms to evaluate the linear discrepancy of certain matrices. For (1), we show that linear discrepancy is $\mathsf{NP}$-hard. Thus we do not expect to find an efficient exact algorithm for the general case. Restricting our attention to matrices with a constant number of rows, we present a poly-time exact algorithm for matrices consisting of a single row and matrices with a constant number of rows and entries of bounded magnitude. We also present an exponential-time approximation algorithm for general matrices, and an algorithm that approximates linear discrepancy to within an exponential factor.
