Moritz Venzin

activity

20192025

most citedApproximation Algorithms for Combinatorial Optimization with Predictions

1 citations · 1 across the 8 of their papers we have counts for

collaborators

9 papers

cs.DS2025

To buy or not to buy: deterministic rent-or-buy problems on node-weighted graphs

Sander Borst, Moritz Venzin

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 ˉ$ non-zero node-weights, and at mo…

cs.DS2025

Learning-Augmented Online Covering Problems

Afrouz Jabal Ameli, Laura Sanita, Moritz Venzin

We give a very general and simple framework to incorporate predictions on requests for online covering problems in a rigorous and black-box manner. Our framework turns any online a…

cs.DS2024★ 1 cited

Approximation Algorithms for Combinatorial Optimization with Predictions

Antonios Antoniadis, Marek Eliáš, Adam Polak +1

We initiate a systematic study of utilizing predictions to improve over approximation guarantees of classic algorithms, without increasing the running time. We propose a systematic…

cs.DS2024

Stronger adversaries grow cheaper forests: online node-weighted Steiner problems

Sander Borst, Marek Eliáš, Moritz Venzin

We propose a $O (lo g k lo g n)$ -competitive randomized algorithm for online node-weighted Steiner forest. This is essentially optimal and significantly improves over the previous b…

cs.DS2021

Approximate $CVP$ in time $2^{0.802 n}$ -- now in any norm!

Thomas Rothvoss, Moritz Venzin

We show that a constant factor approximation of the shortest and closest lattice vector problem in any norm can be computed in time $2^{0.802 n}$ . This contrasts the correspondin…

cs.CG2021

A QPTAS for stabbing rectangles

Friedrich Eisenbrand, Martina Gallato, Ola Svensson +1

We consider the following geometric optimization problem: Given $n$ axis-aligned rectangles in the plane, the goal is to find a set of horizontal segments of minimum total length…

cs.DS2020

Efficient sequential and parallel algorithms for multistage stochastic integer programming using proximity

Jana Cslovjecsek, Friedrich Eisenbrand, Michał Pilipczuk +2

We consider the problem of solving integer programs of the form $min {c^{⊺} x : A x = b, x \geq 0}$ , where $A$ is a multistage stochastic matrix in the following sens…

cs.CG2020

Approximate $CVP_{p}$ in time $2^{0.802 n}$

Friedrich Eisenbrand, Moritz Venzin

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…

cs.DS2019

Covering convex bodies and the Closest Vector Problem

Márton Naszódi, Moritz Venzin

We present algorithms for the $(1 + ε)$ -approximate version of the closest vector problem for certain norms. The currently fastest algorithm (Dadush and Kun 2016) for general norms h…