Source author record

Jens Vygen

Jens Vygen appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Data Structures and Algorithms Discrete Mathematics math.CO

Catalog footprint

What is connected

5works

3topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2016arXiv

Reassembling trees for the traveling salesman

Many recent approximation algorithms for different variants of the traveling salesman problem (asymmetric TSP, graph TSP, s-t-path TSP) exploit the well-known fact that a solution of the natural linear programming relaxation can be written as convex combination of spanning trees. The main argument then is that randomly sampling a tree from such a distribution and then completing the tree to a tour at minimum cost yields a better approximation guarantee than simply taking a minimum cost spanning tree (as in Christofides' algorithm). We argue that an additional step can help: reassembling the spanning trees before sampling. Exchanging two edges in a pair of spanning trees can improve their properties under certain conditions. We demonstrate the usefulness for the metric s-t-path TSP by devising a deterministic polynomial-time algorithm that improves on Sebő's previously best approximation ratio of 8/5.

preprint2016arXiv

Two-connected spanning subgraphs with at most $\frac{10}{7}$OPT edges

We present a $\frac{10}{7}$-approximation algorithm for the minimum two-vertex-connected spanning subgraph problem.

preprint2015arXiv

Better $s$-$t$-Tours by Gao Trees

We consider the $s$-$t$-path TSP: given a finite metric space with two elements $s$ and $t$, we look for a path from $s$ to $t$ that contains all the elements and has minimum total distance. We improve the approximation ratio for this problem from 1.599 to 1.566. Like previous algorithms, we solve the natural LP relaxation and represent an optimum solution $x^*$ as a convex combination of spanning trees. Gao showed that there exists a spanning tree in the support of $x^*$ that has only one edge in each narrow cut (i.e., each cut $C$ with $x^*(C)<2$). Our main theorem says that the spanning trees in the convex combination can be chosen such that many of them are such "Gao trees''.

preprint2015arXiv

Dijkstra meets Steiner: a fast exact goal-oriented Steiner tree algorithm

We present a new exact algorithm for the Steiner tree problem in edge-weighted graphs. Our algorithm improves the classical dynamic programming approach by Dreyfus and Wagner. We achieve a significantly better practical performance via pruning and future costs, a generalization of a well-known concept to speed up shortest path computations. Our algorithm matches the best known worst-case run time and has a fast, often superior, practical performance: on some large instances originating from VLSI design, previous best run times are improved upon by orders of magnitudes. We are also able to solve larger instances of the $d$-dimensional rectilinear Steiner tree problem for $d \in \{3, 4, 5\}$, whose Hanan grids contain up to several millions of edges.

preprint2012arXiv

Shorter Tours by Nicer Ears: 7/5-approximation for graphic TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs

We prove new results for approximating the graphic TSP and some related problems. We obtain polynomial-time algorithms with improved approximation guarantees. For the graphic TSP itself, we improve the approximation ratio to 7/5. For a generalization, the connected-$T$-join problem, we obtain the first nontrivial approximation algorithm, with ratio 3/2. This contains the graphic $s$-$t$-path-TSP as a special case. Our improved approximation guarantee for finding a smallest 2-edge-connected spanning subgraph is 4/3. The key new ingredient of all our algorithms is a special kind of ear-decomposition optimized using forest representations of hypergraphs. The same methods also provide the lower bounds (arising from LP relaxations) that we use to deduce the approximation ratios.