Search Results

Documents authored by Venzin, Moritz

Document
DOI: 10.4230/LIPIcs.ESA.2021.33
Efficient Sequential and Parallel Algorithms for Multistage Stochastic Integer Programming Using Proximity

Authors: Jana Cslovjecsek, Friedrich Eisenbrand, Michał Pilipczuk, Moritz Venzin, and Robert Weismantel

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)

Abstract
We consider the problem of solving integer programs of the form min {c^⊺ x : Ax = b, x ∈ ℤ_{⩾ 0}}, where A is a multistage stochastic matrix in the following sense: the primal treedepth of A is bounded by a parameter d, which means that the columns of A can be organized into a rooted forest of depth at most d so that columns not bound by the ancestor/descendant relation do not have non-zero entries in the same row. We give an algorithm that solves this problem in fixed-parameter time f(d,‖A‖_{∞})⋅ nlog^{𝒪(2^d)} n, where f is a computable function and n is the number of rows of A. The algorithm works in the strong model, where the running time only measures unit arithmetic operations on the input numbers and does not depend on their bitlength. This is the first fpt algorithm for multistage stochastic integer programming to achieve almost linear running time in the strong sense. For two-stage stochastic integer programs, our algorithm works in time 2^{((r+s)‖A‖_∞)^{𝒪(r(r+s))}}⋅ nlog^{𝒪(rs)} n, which improves over previous methods both in terms of the polynomial factor and in terms of the dependence on r and s. In fact, for r = 1 the dependence on s is asymptotically almost tight assuming the Exponential Time Hypothesis. Our algorithm can be also parallelized: we give an implementation in the PRAM model that achieves running time f(d,‖A‖_{∞})⋅ log^{𝒪(2^d)} n using n processors. The main conceptual ingredient in our algorithms is a new proximity result for multistage stochastic integer programs. We prove that if we consider an integer program P, say with a constraint matrix A, then for every optimum solution to the linear relaxation of P there exists an optimum (integral) solution to P that lies, in the 𝓁_{∞}-norm, within distance bounded by a function of ‖A‖_{∞} and the primal treedepth of A. On the way to achieve this result, we prove a generalization and considerable improvement of a structural result of Klein for multistage stochastic integer programs. Once the proximity results are established, this allows us to apply a treedepth-based branching strategy guided by an optimum solution to the linear relaxation.
Cite as

Jana Cslovjecsek, Friedrich Eisenbrand, Michał Pilipczuk, Moritz Venzin, and Robert Weismantel. Efficient Sequential and Parallel Algorithms for Multistage Stochastic Integer Programming Using Proximity. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 33:1-33:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{cslovjecsek_et_al:LIPIcs.ESA.2021.33,
  author =	{Cslovjecsek, Jana and Eisenbrand, Friedrich and Pilipczuk, Micha{\l} and Venzin, Moritz and Weismantel, Robert},
  title =	{{Efficient Sequential and Parallel Algorithms for Multistage Stochastic Integer Programming Using Proximity}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{33:1--33:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.33},
  URN =		{urn:nbn:de:0030-drops-146146},
  doi =		{10.4230/LIPIcs.ESA.2021.33},
  annote =	{Keywords: parameterized algorithm, multistage stochastic programming, proximity}
}
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.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}
}
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