2 Search Results for "Hunkenschröder, Christoph"

Document
DOI: 10.4230/LIPIcs.ESA.2020.43
Approximate CVP_p in Time 2^{0.802 n}

Authors: Friedrich Eisenbrand and Moritz Venzin

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

Abstract
We show that a constant factor approximation of the shortest and closest lattice vector problem w.r.t. any 𝓁_p-norm can be computed in time 2^{(0.802 +ε) n}. This matches the currently fastest constant factor approximation algorithm for the shortest vector problem w.r.t. 𝓁₂. To obtain our result, we combine the latter algorithm w.r.t. 𝓁₂ with geometric insights related to coverings.
Cite as

Friedrich Eisenbrand and Moritz Venzin. Approximate CVP_p in Time 2^{0.802 n}. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 43:1-43:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{eisenbrand_et_al:LIPIcs.ESA.2020.43,
  author =	{Eisenbrand, Friedrich and Venzin, Moritz},
  title =	{{Approximate CVP\underlinep in Time 2^\{0.802 n\}}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{43:1--43:15},
  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.43},
  URN =		{urn:nbn:de:0030-drops-129097},
  doi =		{10.4230/LIPIcs.ESA.2020.43},
  annote =	{Keywords: Shortest and closest vector problem, approximation algorithm, sieving, covering convex bodies}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.49
Faster Algorithms for Integer Programs with Block Structure

Authors: Friedrich Eisenbrand, Christoph Hunkenschröder, and Kim-Manuel Klein

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
We consider integer programming problems max {c^Tx : A x = b, l <= x <= u, x in Z^{nt}} where A has a (recursive) block-structure generalizing n-fold integer programs which recently received considerable attention in the literature. An n-fold IP is an integer program where A consists of n repetitions of submatrices A in Z^{r × t} on the top horizontal part and n repetitions of a matrix B in Z^{s × t} on the diagonal below the top part. Instead of allowing only two types of block matrices, one for the horizontal line and one for the diagonal, we generalize the n-fold setting to allow for arbitrary matrices in every block. We show that such an integer program can be solved in time n^2t^2 phi x (r s delta)^{O(rs^2+ sr^2)} (ignoring logarithmic factors). Here delta is an upper bound on the largest absolute value of an entry of A and phi is the largest binary encoding length of a coefficient of c. This improves upon the previously best algorithm of Hemmecke, Onn and Romanchuk that runs in time n^3t^3 phi x delta^{O(st(r+t))}. In particular, our algorithm is not exponential in the number t of columns of A and B. Our algorithm is based on a new upper bound on the l_1-norm of an element of the Graver basis of an integer matrix and on a proximity bound between the LP and IP optimal solutions tailored for IPs with block structure. These new bounds rely on the Steinitz Lemma. Furthermore, we extend our techniques to the recently introduced tree-fold IPs, where we again present a more efficient algorithm in a generalized setting.
Cite as

Friedrich Eisenbrand, Christoph Hunkenschröder, and Kim-Manuel Klein. Faster Algorithms for Integer Programs with Block Structure. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 49:1-49:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{eisenbrand_et_al:LIPIcs.ICALP.2018.49,
  author =	{Eisenbrand, Friedrich and Hunkenschr\"{o}der, Christoph and Klein, Kim-Manuel},
  title =	{{Faster Algorithms for Integer Programs with Block Structure}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{49:1--49:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.49},
  URN =		{urn:nbn:de:0030-drops-90537},
  doi =		{10.4230/LIPIcs.ICALP.2018.49},
  annote =	{Keywords: n-fold, Tree-fold, Integer Programming}
}
  • Refine by Author
  • 2 Eisenbrand, Friedrich
  • 1 Hunkenschröder, Christoph
  • 1 Klein, Kim-Manuel
  • 1 Venzin, Moritz

  • Refine by Classification
  • 1 Theory of computation → Approximation algorithms analysis
  • 1 Theory of computation → Integer programming
  • 1 Theory of computation → Randomness, geometry and discrete structures

  • Refine by Keyword
  • 1 Integer Programming
  • 1 Shortest and closest vector problem
  • 1 Tree-fold
  • 1 approximation algorithm
  • 1 covering convex bodies
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2018
  • 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