Search Results

Documents authored by Venzin, Moritz

Document
DOI: 10.4230/LIPIcs.STACS.2026.16
To Buy or Not to Buy: Online Rent-Or-Buy on Node-Weighted Graphs

Authors: Sander Borst and Moritz Venzin

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
We study the rent-or-buy variant of the online Steiner forest problem on node- and edge-weighted graphs. For n-node graphs with at most ̄{n} nodes of non-zero weight, and at most k̃ different arriving terminal pairs, we obtain the following: - A deterministic, O(log n log ̄{n})-competitive algorithm against adaptive adversaries. This improves on the previous best, O(log⁴ n)-competitive algorithm obtained by the black-box reduction from [Yair Bartal et al., 2001] combined with the previously best deterministic algorithms for the simpler "buy-only" setting. - A deterministic, O(̄{n}log k̃)-competitive algorithm against adaptive adversaries. This generalizes the O(log k̃)-competitive algorithm for the purely edge-weighted setting from [Seeun Umboh, 2015]. - A randomized, O(log k̃ log ̄{n})-competitive algorithm against oblivious adversaries. All previous approaches were based on the randomized, black-box reduction from [Awerbuch et al., 2004] that achieves a O(log k̃ log n)-competitive ratio when combined with an algorithm for the "buy-only" setting. Our key technical ingredient is a novel charging scheme to an instance of online prize-collecting set cover. This allows us to extend the witness-technique of [Seeun Umboh, 2015] to the node-weighted setting and obtain refined guarantees with respect to ̄{n}, already in the much simpler "buy-only" setting.
Cite as

Sander Borst and Moritz Venzin. To Buy or Not to Buy: Online Rent-Or-Buy on Node-Weighted Graphs. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 16:1-16:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{borst_et_al:LIPIcs.STACS.2026.16,
  author =	{Borst, Sander and Venzin, Moritz},
  title =	{{To Buy or Not to Buy: Online Rent-Or-Buy on Node-Weighted Graphs}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{16:1--16:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.16},
  URN =		{urn:nbn:de:0030-drops-255054},
  doi =		{10.4230/LIPIcs.STACS.2026.16},
  annote =	{Keywords: online network design, node-weighted Steiner forest, derandomization}
}
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}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact