1 Search Results for "Li, Lily"

Document
DOI: 10.4230/LIPIcs.ESA.2020.69
On the Computational Complexity of Linear Discrepancy

Authors: Lily Li and Aleksandar Nikolov

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)

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.
Cite as

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)

Copy BibTex To Clipboard

@InProceedings{li_et_al:LIPIcs.ESA.2020.69,
  author =	{Li, Lily and Nikolov, Aleksandar},
  title =	{{On the Computational Complexity of Linear Discrepancy}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{69:1--69:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.69},
  URN =		{urn:nbn:de:0030-drops-129352},
  doi =		{10.4230/LIPIcs.ESA.2020.69},
  annote =	{Keywords: discrepancy theory, linear discrepancy, rounding, NP-hardness}
}
  • Refine by Author
  • 1 Li, Lily
  • 1 Nikolov, Aleksandar

  • Refine by Classification
  • 1 Theory of computation → Design and analysis of algorithms

  • Refine by Keyword
  • 1 NP-hardness
  • 1 discrepancy theory
  • 1 linear discrepancy
  • 1 rounding

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2020

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 Imprint Privacy Contact