Discrepancy Minimization
- Constructive Discrepancy Minimization by Walking on The Edges
Ragu Meka, Shachar Lovett
Description: Flexible technique for finding partial colorings in any
(symmetric) polytope via a simple random walk. Allows one to specify the desired
error bounds on each constraint, for which a partial coloring is guaranteed to
exist, as long as the error bounds satisfy a certain summability condition.
- Constructive Discrepancy
Minimization in Convex Sets
Thomas Rothvoss
Description: Perhaps the most general method for finding partial colorings
which works for any ``large enough'' symmetric convex body. The method works by
sampling a random Gaussian vector and computing its Euclidean projection on the
feasible region.
- Efficient Algorithms for
Discrepancy Minimization in Convex Sets
Mohit Singh, Ronen Eldan
Description: This work provides a somewhat simpler and more computationally
tractable method for finding partial colorings in (symmetric) convex sets than
that of Rothvoss, which achieves analoguous guarantees. In particular, they simply take the partial coloring to be the
optimal solution one gets by maximizing a random linear functional over the feasible region.
- The Gram-Schmidt Walk: A Cure for
the Banazczyk Blues
Nikhil Bansal, Daniel Dadush, Shashwat Garg, Shachar Lovett
Description: Outputs a random coloring for which the output distribution
is subgaussian. This method is extremely simple and is based on the Gram-Schmidt
orthogonalization of the vectors.
- A Logarithmic Additive
Integrality Gap for Bin Packing
Rebecca Hoberg, Thomas Rothvoss
Description: Gives an application of discrepancy techniques, in particular
the Lovett-Meka partial coloring algorithm, to improve on the additive
integrality gap for the classical bin packing configuration LP.
Rounding Heuristics for IP
Other references we should mention? Please email your
suggestions to Daniel Dadush (dndadush@gmail.com).
|
