4 citations · 8 across the 10 of their papers we have counts for
8 papers · 1 filter
Approximating Multiple-Depot Capacitated Vehicle Routing via LP Rounding
Zachary Friggstad, Tobias Mömke
In Capacitated Vehicle Routing with Multiple Depots (CVRP-MD) we are given a set of client locations and a set of depots located in a metric space with costs betwe…
Approximating Graphic Multi-Path TSP and Graphic Ordered TSP
Morteza Alimi, Niklas Dahlmeier, Tobias Mömke +2
The path version of the Traveling Salesman Problem is one of the most well-studied variants of the ubiquitous TSP. Its generalization, the Multi-Path TSP, has recently been used in…
A Linear Time Gap-ETH-Tight Approximation Scheme for Euclidean TSP
Tobias Mömke, Hang Zhou
The Traveling Salesman Problem (TSP) in the -dimensional Euclidean space is among the oldest and most famous NP-hard optimization problems. In breakthrough works, Arora [J. ACM…
Approximating Traveling Salesman Problems Using a Bridge Lemma
Martin Böhm, Zachary Friggstad, Tobias Mömke +1
We give improved approximations for two metric Traveling Salesman Problem (TSP) variants. In Ordered TSP (OTSP) we are given a linear ordering on a subset of nodes $o_1, \ldots, o_…
A 2-Approximation for the Bounded Treewidth Sparsest Cut Problem in FPT Time
Vincent Cohen-Addad, Tobias Mömke, Victor Verdugo
In the non-uniform sparsest cut problem, we are given a supply graph G and a demand graph D, both with the same set of nodes V. The goal is to find a cut of V that minimizes the ra…
Maximum Scatter TSP in Doubling Metrics
László Kozma, Tobias Mömke
We study the problem of finding a tour of points in which every edge is long. More precisely, we wish to find a tour that visits every point exactly once, maximizing the length…
An Improved Approximation Algorithm for the Traveling Salesman Problem with Relaxed Triangle Inequality
Tobias Mömke
Given a complete edge-weighted graph G, we present a polynomial time algorithm to compute a degree-four-bounded spanning Eulerian subgraph of 2G that has at most 1.5 times the weig…
Improved integrality gap upper bounds for TSP with distances one and two
Matthias Mnich, Tobias Mömke
We study the structure of solutions to linear programming formulations for the traveling salesperson problem (TSP). We perform a detailed analysis of the support of the subtour eli…