Discrepancy without partial colorings

DOI10.4230/LIPICS.APPROX-RANDOM.2014.258zbMATH Open1359.68294OpenAlexW2240692020MaRDI QIDQ2969622FDOQ2969622

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

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

zbMATH Keywords

randomized algorithmsemidefinite programmingBrownian motioncombinatorial discrepancy

Mathematics Subject Classification ID

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

Cited In (8)

• Algorithmic discrepancy beyond partial coloring
• Title not available (Why is that?)
• A remark on Kashin's discrepancy argument and partial coloring in the Komlós conjecture
• Discrepancy theory and related algorithms
• Constructive discrepancy minimization by walking on the edges
• Multicolour Discrepancies
• An algorithm for Komlós conjecture matching Banaszczyk's bound
• Gaussian discrepancy: a probabilistic relaxation of vector balancing

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)