68 citations · 142 across the 43 of their papers we have counts for
Showing 2018Show all
3 papers · 1 filter
cs.DS2018
Approximate Multi-Matroid Intersection via Iterative Refinement
André Linhares, Neil Olver, Chaitanya Swamy +1
We introduce a new iterative rounding technique to round a point in a matroid polytope subject to further matroid constraints. This technique returns an independent set in one matr…
cs.DM2018
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,…
cs.DS2018
Improved Approximation for Tree Augmentation: Saving by Rewiring
Fabrizio Grandoni, Christos Kalaitzis, Rico Zenklusen
The Tree Augmentation Problem (TAP) is a fundamental network design problem in which we are given a tree and a set of additional edges, also called \emph{links}. The task is to fin…