4 citations · 8 across the 10 of their papers we have counts for
12 papers
V844 Herculis: An Exceptional Intermediate Polar Hiding in an Ordinary Dwarf Nova
Anousha Greiveldinger, Peter Garnavich, Colin Littlefield +16
We present time-series spectroscopy of the SU UMa-type dwarf nova V844 Her during quiescence. We discover high-velocity Balmer and He I emission features modulated at a period of 2…
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_…
Approximating Maximum Edge 2-Coloring by Normalizing Graphs
Tobias Mömke, Alexandru Popa, Aida Roshany-Tabrizi +2
In a simple, undirected graph G, an edge 2-coloring is a coloring of the edges such that no vertex is incident to edges with more than 2 distinct colors. The problem maximum edge 2…
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…
A (2+ε)-Approximation Algorithm for Maximum Independent Set of Rectangles
Waldo Gálvez, Arindam Khan, Mathieu Mari +3
We study the Maximum Independent Set of Rectangles (MISR) problem, where we are given a set of axis-parallel rectangles in the plane and the goal is to select a subset of non-overl…
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…
Complexity and Approximability of Parameterized MAX-CSPs
Holger Dell, Eun Jung Kim, Michael Lampis +2
We study the optimization version of constraint satisfaction problems (Max-CSPs) in the framework of parameterized complexity; the goal is to compute the maximum fraction of constr…
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…