Deterministic discrepancy minimization via the multiplicative weight update method

DOI10.1007/978-3-319-59250-3_31zbMath1418.05127arXiv1611.08752OpenAlexW2558885861MaRDI QIDQ2401177

Harishchandra Ramadas, Avi Levy, Thomas Rothvoß

Publication date: 31 August 2017

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

zbMATH Keywords

pigeonhole principletwo-coloringprobabilistic techniquesRudin-Shapiro functions

Mathematics Subject Classification ID

Integer programming (90C10) Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Combinatorial optimization (90C27) Approximation algorithms (68W25) Ramsey theory (05D10)

Related Items (9)

Almost envy-freeness for groups: improved bounds via discrepancy theory ⋮ The Phase Transition of Discrepancy in Random Hypergraphs ⋮ Vector balancing in Lebesgue spaces ⋮ Discrepancy theory and related algorithms ⋮ Maximizing coverage while ensuring fairness: a tale of conflicting objectives ⋮ An Algorithm for Komlós Conjecture Matching Banaszczyk's Bound ⋮ Unnamed Item ⋮ Gaussian discrepancy: a probabilistic relaxation of vector balancing ⋮ Upper and lower bounds for matrix discrepancy

This page was built for publication: Deterministic discrepancy minimization via the multiplicative weight update method