Approximating Hereditary Discrepancy via Small Width Ellipsoids

DOI10.1137/1.9781611973730.24zbMath1371.11121arXiv1311.6204OpenAlexW2949210153MaRDI QIDQ5363034

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

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

Related Items (9)

An Improved Private Mechanism for Small Databases ⋮ Approximation-Friendly Discrepancy Rounding ⋮ Proportional Volume Sampling and Approximation Algorithms for A-Optimal Design ⋮ The discrepancy of random rectangular matrices ⋮ TIGHTER BOUNDS FOR THE DISCREPANCY OF BOXES AND POLYTOPES ⋮ Unnamed Item ⋮ An Algorithm for Komlós Conjecture Matching Banaszczyk's Bound ⋮ The Geometry of Differential Privacy: The Small Database and Approximate Cases ⋮ On a new method for controlling the entire spectrum in the problem of column subset selection

This page was built for publication: Approximating Hereditary Discrepancy via Small Width Ellipsoids