Discrepancy and Approximation Algorithms
summary
Shows that linear discrepancy (worst-case rounding error from fractional LP solutions) is bounded by hereditary discrepancy and that this yields concrete rounding routines: a partial coloring algorithm (random-walk/LP directions) fixes a constant fraction of variables per phase so rounding finishes in O(log n) phases, and applying a modified matrix gives bin‑packing guarantees of roughly +O(log OPT) bins for constant‑size items. Uses Banaszczyk’s theorem (algorithmized) to get O(sqrt(log m)) discrepancy bounds; computing discrepancy remains NP‑hard in strong regimes, while hereditary discrepancy admits polylog approximations.
AI-written summary · about