Approximating hereditary discrepancy via small width ellipsoids

DOI10.1137/1.9781611973730.24MaRDI QIDQ5363034zbMATH OpenOpenAlexFDO

Authors Aleksandar Nikolov, Kunal Talwar

Publication date 5 October 2017

Published in Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1311.6204

Mathematics Subject Classification ID

Hypergraphs (05C65) Irregularities of distribution, discrepancy (11K38) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Applications of mathematical programming (90C90)

Abstract: 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 $ildeO(lo{g}^{3}n)$-approximation to hereditary discrepancy, as a by-product of their work in differential privacy. In this paper, we give a direct simple $O(lo{g}^{3/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 $el{l}_{infty}$ norm of any point in a ellipsoid containing the columns of $A$. This characterization promises to be a useful tool in discrepancy theory.

Recommendations

• Factorization norms and hereditary discrepancy
• The determinant bound for discrepancy is almost tight
• A trace bound for the hereditary discrepancy
• Linear and hereditary discrepancy
• Deterministic discrepancy minimization

Cited in

(10)

• On a new method for controlling the entire spectrum in the problem of column subset selection
• An improved private mechanism for small databases
• Tighter bounds for the discrepancy of boxes and polytopes
• An algorithm for Komlós conjecture matching Banaszczyk's bound
• Proportional volume sampling and approximation algorithms for \(A\)-optimal design
• Constructive discrepancy minimization with hereditary L2 guarantees
• Factorization norms and hereditary discrepancy
• The discrepancy of random rectangular matrices
• scientific article; zbMATH DE number 7758358 (Why is no real title available?)
• On the gap between hereditary discrepancy and the determinant lower bound

This page was built for publication: Approximating hereditary discrepancy via small width ellipsoids

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5363034)