Algorithmic discrepancy beyond partial coloring

DOI10.1145/3055399.3055490MaRDI QIDQ4978034zbMATH OpenOpenAlexFDO

Authors N. Bansal, Shashwat Garg

Publication date 17 August 2017

Published in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

discrepancyrandom walksrounding techniquessemidefinite programming

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Semidefinite programming (90C22)

Abstract: The partial coloring method is one of the most powerful and widely used method in combinatorial discrepancy problems. However, in many cases it leads to sub-optimal bounds as the partial coloring step must be iterated a logarithmic number of times, and the errors can add up in an adversarial way. We give a new and general algorithmic framework that overcomes the limitations of the partial coloring method and can be applied in a black-box manner to various problems. Using this framework, we give new improved bounds and algorithms for several classic problems in discrepancy. In particular, for Tusnady's problem, we give an improved $O(lo{g}^{2}n)$ bound for discrepancy of axis-parallel rectangles and more generally an $O_d(lo{g}^{d}n)$ bound for $d$-dimensional boxes in $mathbb{R}^d$. Previously, even non-constructively, the best bounds were $O(lo{g}^{2.5}n)$ and $O_d(lo{g}^{d+0.5}n)$ respectively. Similarly, for the Steinitz problem we give the first algorithm that matches the best known non-constructive bounds due to Banaszczyk [Banaszczyk 2012] in the $el{l}_{i}nfty$ case, and improves the previous algorithmic bounds substantially in the $el{l}_2$ case. Our framework is based upon a substantial generalization of the techniques developed recently in the context of the Koml'os discrepancy problem [BDG16].

Recommendations

• On the discrepancy of coloring finite sets
• Discrepancy without partial colorings
• Algorithmic bounds for the chromatic number†
• Algorithmic aspects of partial list colourings
• Algorithmic aspects of combinatorial discrepancy
• The chromatic discrepancy of graphs
• An exact algorithm for the partition coloring problem
• Polynomial-time approximation algorithms for the coloring problem in some cases
• scientific article; zbMATH DE number 7650095

Cited in

(10)

• Tighter bounds for the discrepancy of boxes and polytopes
• An algorithm for Komlós conjecture matching Banaszczyk's bound
• Constructive discrepancy minimization with hereditary L2 guarantees
• A Spectral Approach to Network Design
• scientific article; zbMATH DE number 7205030 (Why is no real title available?)
• Multicolor Discrepancy of Arithmetic Structures
• Discrepancy theory and related algorithms
• Revisit the partial coloring method: prefix spencer and sampling
• Smoothed analysis with adaptive adversaries
• Discrepancy minimization via a self-balancing walk

This page was built for publication: Algorithmic discrepancy beyond partial coloring

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