3 citations · 4 across the 5 of their papers we have counts for
6 papers · 1 filter
On the Complexity of the Odd-Red Bipartite Perfect Matching Polytope
Martin Nägele, Christian Nöbel, Rico Zenklusen
The odd-red bipartite perfect matching problem asks to find a perfect matching containing an odd number of red edges in a given red-blue edge-colored bipartite graph. While this pr…
A Better-Than-1.6-Approximation for Prize-Collecting TSP
Jannis Blauth, Nathan Klein, Martin Nägele
Prize-Collecting TSP is a variant of the traveling salesperson problem where one may drop vertices from the tour at the cost of vertex-dependent penalties. The quality of a solutio…
Advances on Strictly -Modular IPs
Martin Nägele, Christian Nöbel, Richard Santiago +1
There has been significant work recently on integer programs (IPs) with a constraint marix with bounded subdeterminants.…
A New Dynamic Programming Approach for Spanning Trees with Chain Constraints and Beyond
Martin Nägele, Rico Zenklusen
Short spanning trees subject to additional constraints are important building blocks in various approximation algorithms. Especially in the context of the Traveling Salesman Proble…
An improved approximation guarantee for Prize-Collecting TSP
Jannis Blauth, Martin Nägele
We present a new approximation algorithm for the (metric) prize-collecting traveling salesperson problem (PCTSP). In PCTSP, opposed to the classical traveling salesperson problem (…
Submodular Minimization Under Congruency Constraints
Martin Nägele, Benny Sudakov, Rico Zenklusen
Submodular function minimization (SFM) is a fundamental and efficiently solvable problem class in combinatorial optimization with a multitude of applications in various fields. Sur…