Skip to main content
Log in

Deterministic Discrepancy Minimization

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

We derandomize a recent algorithmic approach due to Bansal (Foundations of Computer Science, FOCS, pp. 3–10, 2010) to efficiently compute low discrepancy colorings for several problems, for which only existential results were previously known. In particular, we give an efficient deterministic algorithm for Spencer’s six standard deviations result (Spencer in Trans. Am. Math. Soc. 289:679–706, 1985), and to find a low discrepancy coloring for a set system with low hereditary discrepancy.

The main new idea is to add certain extra constraints to the natural semidefinite programming formulation for discrepancy, which allow us to argue about the existence of a good deterministic move at each step of the algorithm. The non-constructive entropy method is used to argue the feasibility of this enhanced SDP.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Notes

  1. For general m, we can also obtain the bound \(O(\sqrt{n} \log(m/n))\) as in [2], but to we restrict our attention here to m=O(n) which is the most interesting case.

References

  1. Alon, N., Spencer, J.H.: The Probabilistic Method, 2nd edn. Wiley, New York (2000)

    Book  MATH  Google Scholar 

  2. Bansal, N.: Constructive algorithms for discrepancy minimization. In: Foundations of Computer Science, FOCS, pp. 3–10 (2010). arXiv:1002.2259

    Google Scholar 

  3. Beck, J.: Roth’s estimate on the discrepancy of integer sequences is nearly sharp. Combinatorica 1, 319–325 (1981)

    Article  MathSciNet  MATH  Google Scholar 

  4. Chazelle, B.: The Discrepancy Method: Randomness and Complexity. Cambridge University Press, Cambridge (2001)

    Google Scholar 

  5. Doerr, B.: Linear and hereditary discrepancy. Comb. Probab. Comput. 9(4), 349–354 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  6. Drmota, M., Tichy, R.F.: Sequences, Discrepancies and Applications. Springer, Berlin (1997)

    MATH  Google Scholar 

  7. Engebretsen, L., Indyk, P., O’Donnell, R.: Derandomized dimensionality reduction with applications. In: ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 705–712 (2002)

    Google Scholar 

  8. Kim, J.H., Matoušek, J., Vu, V.H.: Discrepancy after adding a single set. Combinatorica 25(4), 499–501 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  9. Lovász, L., Spencer, J., Vesztergombi, K.: Discrepancy of set-systems and matrices. Eur. J. Comb. 7, 151–160 (1986)

    Article  MATH  Google Scholar 

  10. Mahajan, S., Ramesh, H.: Derandomizing approximation algorithms based on semidefinite programming. SIAM J. Comput. 28(5), 1641–1663 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  11. Matoušek, J.: The determinant bound for discrepancy is almost tight. Manuscript. arXiv:1101.0767

  12. Matoušek, J.: An p version of the Beck-Fiala conjecture. Eur. J. Comb. 19, 175–182 (1998)

    Article  MATH  Google Scholar 

  13. Matoušek, J.: Geometric Discrepancy: An Illustrated Guide. Springer, Berlin (2010)

    Google Scholar 

  14. Raghavan, P.: Probabilistic construction of deterministic algorithms: approximating packing integer programs. J. Comput. Syst. Sci. 37(2), 130–143 (1988)

    Article  MathSciNet  MATH  Google Scholar 

  15. Sivakumar, D.: Algorithmic derandomization via complexity theory. In: ACM Symposium on Theory of Computing, STOC, pp. 619–626 (2002)

    Google Scholar 

  16. Spencer, J.: Balancing games. J. Comb. Theory, Ser. B 23(1), 68–74 (1977)

    Article  MATH  Google Scholar 

  17. Spencer, J.: Six standard deviations suffice. Trans. Am. Math. Soc. 289(2), 679–706 (1985)

    Article  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Nikhil Bansal.

Additional information

A preliminary version of this paper appeared in European Symposium on Algorithms, ESA 2011.

This research has been supported by the Netherlands Organisation for Scientific Research (NWO) grant 639.022.211.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Bansal, N., Spencer, J. Deterministic Discrepancy Minimization. Algorithmica 67, 451–471 (2013). https://doi.org/10.1007/s00453-012-9728-1

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-012-9728-1

Keywords

Navigation