Moritz Venzin

activity

20202025

most citedApproximation Algorithms for Combinatorial Optimization with Predictions

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

collaborators

Showing cs.CGShow all

2 papers · 1 filter

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.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…

A QPTAS for stabbing rectangles

Approximate CVPp​ in time 20.802n

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