A Unified Approach to Discrepancy Minimization

2022/05/02 by Bansal, Nikhil, Laddha, Aditi, Vempala, Santosh S. · 3 citations
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2205.01023

Abstract

We study a unified approach and algorithm for constructive discrepancy minimization based on a stochastic process. By varying the parameters of the process, one can recover various state-of-the-art results. We demonstrate the flexibility of the method by deriving a discrepancy bound for smoothed instances, which interpolates between known bounds for worst-case and random instances.

Cited by

• Efficient Algorithms for Partitioning Circulant Graphs with Optimal Spectral Approximation
• Decoupling via Affine Spectral-Independence: Beck-Fiala and Komlós Bounds Beyond Banaszczyk
• An Improved Bound for the Beck-Fiala Conjecture

Related

• Discrepancy Minimization via Regularization
• Discrepancy Minimization via a Self-Balancing Walk
• Algorithmic Discrepancy Minimization
• Constructive Algorithms for Discrepancy Minimization
• Gaussian discrepancy: a probabilistic relaxation of vector balancing