68 citations · 142 across the 43 of their papers we have counts for
8 papers · 1 filter
Reducing Path TSP to TSP
Vera Traub, Jens Vygen, Rico Zenklusen
We present a black-box reduction from the path version of the Traveling Salesman Problem (Path TSP) to the classical tour version (TSP). More precisely, we show that given an -a…
A 1.5-Approximation for Path TSP
Rico Zenklusen
We present a -approximation for the Metric Path Traveling Salesman Problem (Path TSP). All recent improvements on Path TSP crucially exploit a structural property shown by An,…
Lifting Linear Extension Complexity Bounds to the Mixed-Integer Setting
Alfonso Cevallos, Stefan Weltge, Rico Zenklusen
Mixed-integer mathematical programs are among the most commonly used models for a wide set of problems in Operations Research and related fields. However, there is still very littl…
Matroids and Integrality Gaps for Hypergraphic Steiner Tree Relaxations
Michel X. Goemans, Neil Olver, Thomas Rothvoss +1
Until recently, LP relaxations have played a limited role in the design of approximation algorithms for the Steiner tree problem. In 2010, Byrka et al. presented a ln(4)+epsilon ap…
Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes
Chandra Chekuri, Jan Vondrák, Rico Zenklusen
We consider the problem of maximizing a non-negative submodular set function over a ground set subject to a variety of packing type constraints…
Matching Interdiction
Rico Zenklusen
In the matching interdiction problem, we are given an undirected graph with weights and interdiction costs on the edges and seek to remove a subset of the edges constrained to some…
Extensions to Network Flow Interdiction on Planar Graphs
Rico Zenklusen
Network flow interdiction analysis studies by how much the value of a maximum flow in a network can be diminished by removing components of the network constrained to some budget.…
Estimation of Small s-t Reliabilities in Acyclic Networks
Marco Laumanns, Rico Zenklusen
In the classical s-t network reliability problem a fixed network G is given including two designated vertices s and t (called terminals). The edges are subject to independent rando…