Document Open Access Logo

On the Computational Complexity of Linear Discrepancy

Authors Lily Li, Aleksandar Nikolov

PDF
Thumbnail PDF

File

LIPIcs.ESA.2020.69.pdf
  • Filesize: 0.59 MB
  • 16 pages

Document Identifiers

Author Details

Lily Li
  • Department of Computer Science, University of Toronto, Canada
Aleksandar Nikolov
  • Department of Computer Science, University of Toronto, Canada

Funding

This research was supported by an NSERC Discovery Grant (application number RGPIN-2016-06333).

Cite As Get BibTex

Lily Li and Aleksandar Nikolov. On the Computational Complexity of Linear Discrepancy. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 69:1-69:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ESA.2020.69

Abstract

Many problems in computer science and applied mathematics require rounding a vector 𝐰 of fractional values lying in the interval [0,1] to a binary vector 𝐱 so that, for a given matrix 𝐀, 𝐀𝐱 is as close to 𝐀𝐰 as possible. For example, this problem arises in LP rounding algorithms used to approximate NP-hard optimization problems and in the design of uniformly distributed point sets for numerical integration. For a given matrix 𝐀, the worst-case error over all choices of 𝐰 incurred by the best possible rounding is measured by the linear discrepancy of 𝐀, a quantity studied in discrepancy theory, and introduced by Lovasz, Spencer, and Vesztergombi (EJC, 1986).
We initiate the study of the computational complexity of linear discrepancy. Our investigation proceeds in two directions: (1) proving hardness results and (2) finding both exact and approximate algorithms to evaluate the linear discrepancy of certain matrices. For (1), we show that linear discrepancy is NP-hard. Thus we do not expect to find an efficient exact algorithm for the general case. Restricting our attention to matrices with a constant number of rows, we present a poly-time exact algorithm for matrices consisting of a single row and matrices with a constant number of rows and entries of bounded magnitude. We also present an exponential-time approximation algorithm for general matrices, and an algorithm that approximates linear discrepancy to within an exponential factor.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • discrepancy theory
  • linear discrepancy
  • rounding
  • NP-hardness

Metrics

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

References

  1. Christoph Aistleitner, Dmitriy Bilyk, and Aleksandar Nikolov. Tusnády’s problem, the transference principle, and non-uniform qmc sampling. In Art B. Owen and Peter W. Glynn, editors, Monte Carlo and Quasi-Monte Carlo Methods, pages 169-180. Springer International Publishing, 2016. Google Scholar
  2. Per Austrin, Venkatesan Guruswami, and Johan Håstad. (2+ε)-sat is np-hard. SIAM Journal on Computing, 46(5):1554-1573, 2017. Google Scholar
  3. Nikhil Bansal, Ravishankar Krishnaswamy, and Viswanath Nagarajan. Better scalable algorithms for broadcast scheduling. ACM Trans. Algorithms, 11(1):3:1-3:24, 2014. Google Scholar
  4. József Beck and Vera T Sós. Discrepancy theory. In Handbook of combinatorics (vol. 2), pages 1405-1446. MIT Press, 1996. Google Scholar
  5. Jean-Daniel Boissonnat, Micha Sharir, Boaz Tagansky, and Mariette Yvinec. Voronoi diagrams in higher dimensions under certain polyhedral distance functions. Discrete & Computational Geometry, 19(4):485-519, 1998. URL: https://doi.org/10.1007/PL00009366.
  6. Moses Charikar, Alantha Newman, and Aleksandar Nikolov. Tight hardness results for minimizing discrepancy. In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms, pages 1607-1614. Society for Industrial and Applied Mathematics, 2011. Google Scholar
  7. Bernard Chazelle. An optimal convex hull algorithm in any fixed dimension. Discrete & Computational Geometry, 10(4):377-409, 1993. Google Scholar
  8. Bernard Chazelle. The discrepancy method: randomness and complexity. Cambridge University Press, 2001. Google Scholar
  9. E Mark Gold. Complexity of automaton identification from given data. Information and control, 37(3):302-320, 1978. Google Scholar
  10. Venkatesan Guruswami, Daniele Micciancio, and Oded Regev. The complexity of the covering radius problem. Computational Complexity, 14(2):90-121, 2005. Google Scholar
  11. Ishay Haviv and Oded Regev. Hardness of the covering radius problem on lattices. In Computational Complexity, 2006. CCC 2006. Twenty-First Annual IEEE Conference on, pages 14-pp. IEEE, 2006. Google Scholar
  12. Rebecca Hoberg and Thomas Rothvoss. A logarithmic additive integrality gap for bin packing. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2616-2625. SIAM, 2017. Google Scholar
  13. Christian Icking, Rolf Klein, Ngoc-Minh Lé, and Lihong Ma. Convex distance functions in 3-space are different. Fundamenta Informaticae, 22(4):331-352, 1995. Google Scholar
  14. László Lovász, Joel Spencer, and Katalin Vesztergombi. Discrepancy of set-systems and matrices. European Journal of Combinatorics, 7(2):151-160, 1986. Google Scholar
  15. Jiri Matousek. Geometric discrepancy: An illustrated guide. Springer, 1999. Google Scholar
  16. Jiří Matoušek, Aleksandar Nikolov, and Kunal Talwar. Factorization Norms and Hereditary Discrepancy. International Mathematics Research Notices, 2020(3):751-780, March 2018. URL: https://doi.org/10.1093/imrn/rny033.
  17. A. Nikolov. Tighter bounds for the discrepancy of boxes and polytopes. Mathematika, 63(3):1091-1113, 2017. URL: https://doi.org/10.1112/S0025579317000250.
  18. Thomas Rothvoß. Approximating bin packing within o (log opt* log log opt) bins. In Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium on, pages 20-29. IEEE, 2013. Google Scholar
  19. Alexander Schrijver. Theory of linear and integer programming. John Wiley & Sons, 1998. Google Scholar
  20. Godfried T Toussaint. Computing largest empty circles with location constraints. International journal of computer & information sciences, 12(5):347-358, 1983. 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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact