Constructive Discrepancy Minimization with Hereditary L2 Guarantees

Author Kasper Green Larsen



PDF
Thumbnail PDF

File

LIPIcs.STACS.2019.48.pdf
  • Filesize: 0.53 MB
  • 13 pages

Document Identifiers

Author Details

Kasper Green Larsen
  • Department of Computer Science, Aarhus University, Denmark

Acknowledgements

The author wishes to thank Nikhil Bansal for useful discussions and pointers to relevant literature. The author also thanks an anonymous STOC reviewer for comments that simplified the PartialColor algorithm.

Cite AsGet BibTex

Kasper Green Larsen. Constructive Discrepancy Minimization with Hereditary L2 Guarantees. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 48:1-48:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.STACS.2019.48

Abstract

In discrepancy minimization problems, we are given a family of sets S = {S_1,...,S_m}, with each S_i in S a subset of some universe U = {u_1,...,u_n} of n elements. The goal is to find a coloring chi : U -> {-1,+1} of the elements of U such that each set S in S is colored as evenly as possible. Two classic measures of discrepancy are l_infty-discrepancy defined as disc_infty(S,chi):=max_{S in S} | sum_{u_i in S} chi(u_i) | and l_2-discrepancy defined as disc_2(S,chi):=sqrt{(1/|S|) sum_{S in S} (sum_{u_i in S} chi(u_i))^2}. Breakthrough work by Bansal [FOCS'10] gave a polynomial time algorithm, based on rounding an SDP, for finding a coloring chi such that disc_infty(S,chi) = O(lg n * herdisc_infty(S)) where herdisc_infty(S) is the hereditary l_infty-discrepancy of S. We complement his work by giving a clean and simple O((m+n)n^2) time algorithm for finding a coloring chi such disc_2(S,chi) = O(sqrt{lg n} * herdisc_2(S)) where herdisc_2(S) is the hereditary l_2-discrepancy of S. Interestingly, our algorithm avoids solving an SDP and instead relies simply on computing eigendecompositions of matrices. To prove that our algorithm has the claimed guarantees, we also prove new inequalities relating both herdisc_infty and herdisc_2 to the eigenvalues of the incidence matrix corresponding to S. Our inequalities improve over previous work by Chazelle and Lvov [SCG'00] and by Matousek, Nikolov and Talwar [SODA'15+SCG'15]. We believe these inequalities are of independent interest as powerful tools for proving hereditary discrepancy lower bounds. Finally, we also implement our algorithm and show that it far outperforms random sampling of colorings in practice. Moreover, the algorithm finishes in a reasonable amount of time on matrices of sizes up to 10000 x 10000.

Subject Classification

ACM Subject Classification
  • Theory of computation
Keywords
  • Discrepancy
  • Hereditary Discrepancy
  • Combinatorics
  • Computational Geometry

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. R. Alexander. Geometric methods in the study of irregularities of distribution. Combinatorica, 10(2):115-136, 1990. Google Scholar
  2. Wojciech Banaszczyk. Balancing vectors and Gaussian measures of n-dimensional convex bodies. Random Structures &Algorithms, 12:351-360, July 1998. Google Scholar
  3. Nikhil Bansal. Constructive Algorithms for Discrepancy Minimization. In Proc. 51th Annual IEEE Symposium on Foundations of Computer Science (FOCS'10), pages 3-10, 2010. Google Scholar
  4. Nikhil Bansal, Daniel Dadush, and Shashwat Garg. An Algorithm for Komlós Conjecture Matching Banaszczyk’s Bound. In Proc. 57th IEEE Annual Symposium on Foundations of Computer Science (FOCS'16), pages 788-799, 2016. Google Scholar
  5. Nikhil Bansal, Daniel Dadush, Shashwat Garg, and Shachar Lovett. The Gram-Schmidt Walk: A Cure for the Banaszczyk Blues. CoRR, abs/1708.01079, 2017. URL: http://arxiv.org/abs/1708.01079.
  6. Nikhil Bansal and Shashwat Garg. Algorithmic Discrepancy Beyond Partial Coloring. In Proc. 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC), STOC 2017, pages 914-926, 2017. Google Scholar
  7. J. Beck and T. Fiala. Integer-making theorems. Discrete Applied Mathematics, 3:1-8, February 1981. Google Scholar
  8. Moses Charikar, Alantha Newman, and Aleksandar Nikolov. Tight Hardness Results for Minimizing Discrepancy. In Proc. 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '11, pages 1607-1614, 2011. Google Scholar
  9. Bernard Chazelle. The Discrepancy Method: Randomness and Complexity. Cambridge University Press, 2000. Google Scholar
  10. Bernard Chazelle and Alexey Lvov. A Trace Bound for the Hereditary Discrepancy. In Proc. 16th Annual Symposium on Computational Geometry, SCG '00, pages 64-69, 2000. Google Scholar
  11. Kasper Green Larsen. On Range Searching in the Group Model and Combinatorial Discrepancy. SIAM Journal on Computing, 43(2):673-686, 2014. Google Scholar
  12. Avi Levy, Harishchandra Ramadas, and Thomas Rothvoss. Deterministic Discrepancy Minimization via the Multiplicative Weight Update Method. In Integer Programming and Combinatorial Optimization - 19th International Conference, IPCO 2017, Waterloo, ON, Canada, June 26-28, 2017, Proceedings, pages 380-391, 2017. Google Scholar
  13. L. Lovász, J. Spencer, and K. Vesztergombi. Discrepancy of Set-systems and Matrices. European Journal of Combinatorics, 7(2):151-160, 1986. URL: http://dx.doi.org/10.1016/S0195-6698(86)80041-5.
  14. Shachar Lovett and Raghu Meka. Constructive Discrepancy Minimization by Walking on the Edges. SIAM Journal on Computing, 44(5):1573-1582, 2015. Google Scholar
  15. J. Matoušek. Tight Upper Bounds for the Discrepancy of Half-Spaces. Discrete and Computational Geometry, 13:593-601, 1995. Google Scholar
  16. J. Matousek. Geometric Discrepancy: An Illustrated Guide. Algorithms and Combinatorics. Springer Berlin Heidelberg, 1999. Google Scholar
  17. Jirí Matoušek and Aleksandar Nikolov. Combinatorial Discrepancy for Boxes via the gamma_2 Norm. In 31st International Symposium on Computational Geometry (SoCG 2015), volume 34, pages 1-15, 2015. Google Scholar
  18. Jiří Matoušek, Aleksandar Nikolov, and Kunal Talwar. Factorization Norms and Hereditary Discrepancy. CoRR, abs/1408.1376, 2014. URL: http://arxiv.org/abs/1408.1376.
  19. Carl D. Meyer, editor. Matrix Analysis and Applied Linear Algebra. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2000. Google Scholar
  20. Aleksandar Nikolov. Tighter bounds for the discrepancy of boxes and polytopes. Mathematika, 63:1091-1113, 2017. Google Scholar
  21. Joel Spencer. Six standard deviations suffice. Trans. Amer. Math. Soc., 289:679-706, 1985. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail