Approximating Hereditary Discrepancy via Small Width Ellipsoids
Approximating Hereditary Discrepancy via Small Width Ellipsoids
复制标题
通过小宽度椭球近似遗传差异
DOI：
10.1137/1.9781611973730.24
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Kunal Talwar
中科院分区：
文献类型：
--
作者：
Aleksandar Nikolov;Kunal Talwar
超图的差异是在其顶点的两个色彩上的最低可达到的值，这是任何超边缘的最大绝对不平衡。它的顶点是其复杂性的量度。程序，基于遗传差异的基于确定的下限。 ）显示了多项式o（log3 n） - 对遗传差异，作为其在差分隐私中的副产品，我们给出了一个直接的简单o（log3/2 n） - 适用于此问题的算法。包含A的列的椭圆形有望成为差异理论中的有用工具。
The Discrepancy of a hypergraph is the minimum attainable value, over two-colorings of its vertices, of the maximum absolute imbalance of any hyperedge. The Hereditary Discrepancy of a hypergraph, defined as the maximum discrepancy of a restriction of the hypergraph to a subset of its vertices, is a measure of its complexity. Lovasz, Spencer and Vesztergombi (1986) related the natural extension of this quantity to matrices to rounding algorithms for linear programs, and gave a determinant based lower bound on the hereditary discrepancy. Matousek (2011) showed that this bound is tight up to a polylogarithmic factor, leaving open the question of actually computing this bound. Recent work by Nikolov, Talwar and Zhang (2013) showed a polynomial time O(log3 n)-approximation to hereditary discrepancy, as a by-product of their work in differential privacy. In this paper, we give a direct simple O(log3/2 n)-approximation algorithm for this problem. We show that up to this approximation factor, the hereditary discrepancy of a matrix A is characterized by the optimal value of simple geometric convex program that seeks to minimize the largest l∞ norm of any point in a ellipsoid containing the columns of A. This characterization promises to be a useful tool in discrepancy theory.