Moritz Venzin

collaborators

4 papers

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…

Approximate CVP in time 20.802n -- now in any norm!

A QPTAS for stabbing rectangles

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

Approximate CVPp​ in time 20.802n

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

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