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).