Paul Paschmanns

Paul Paschmanns

Some picture ...

I am a PhD student at ETH Zurich, supervised by Vera Traub. Before that I studied math in Bonn and worked as a student assistant at the Research Institute for Discrete Mathematics.

My main research interests are approximation algorithms for combinatorial optimization problems, in particular, primal-dual approaches and network design.

Publications

The Bidirected Cut Relaxation for Steiner Tree: Better Integrality Gap Bounds and the Limits of Moat Growing
with V. Traub
[arXiv]
The Days On Days Off Scheduling Problem
with F. Niessen
EJOR, 2026. [arXiv]

Animations of Bidirected Moat Growing

The main technique used to bound the integrality gap of BCR is a generalization of moat growing to a (bi)directed setting which was introduced here by Byrka, Grandoni, and Traub. Bidirecred moat growing can be quite chaotic and unintuitive, which is why we provide animated versions of the figures in our paper:

Figure 1

Classical undirected dual growth

Figure 2

Two terminal with 2x-speed

Figure 3

Two terminal with 3x-speed

Figure 4

Bad instances (not MST-optimal)

Figure 7

Finding a bifurcation vertex is difficult

Figure 9

Not invariant under subdivision

Figure 11

Meeting points

Contact

Address:	Paul Paschmanns ETH Zurich, OAT Z 28 Andreasstrasse 5 8092 Zurich, CH
E-Mail:	paul.paschmanns (at) inf.ethz.ch