Discrepancy without partial colorings

DOI10.4230/LIPICS.APPROX-RANDOM.2014.258MaRDI QIDQ2969622zbMATH OpenOpenAlexFDO

Authors Nicholas J. A. Harvey, Roy Schwartz, Mohit Singh

Publication date 22 March 2017

Full work available at URL https://research.microsoft.com/en-us/um/people/mohits/publications/discrepancy1.pdf

zbMATH Keywords

Brownian motioncombinatorial discrepancyrandomized algorithmsemidefinite programming

Mathematics Subject Classification ID

Extremal set theory (05D05) Randomized algorithms (68W20) Semidefinite programming (90C22)

Recommendations

• Constructive discrepancy minimization by walking on the edges
• Efficient algorithms for discrepancy minimization in convex sets
• Constructive Discrepancy Minimization for Convex Sets
• Deterministic discrepancy minimization via the multiplicative weight update method
• Algorithmic aspects of combinatorial discrepancy

Cited in

(8)

• Gaussian discrepancy: a probabilistic relaxation of vector balancing
• A remark on Kashin's discrepancy argument and partial coloring in the Komlós conjecture
• Constructive discrepancy minimization by walking on the edges
• Multicolour Discrepancies
• An algorithm for Komlós conjecture matching Banaszczyk's bound
• scientific article; zbMATH DE number 1418265 (Why is no real title available?)
• Algorithmic discrepancy beyond partial coloring
• Discrepancy theory and related algorithms

This page was built for publication: Discrepancy without partial colorings

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