2 citations · 5 across the 6 of their papers we have counts for
6 papers
Layers and Matroids for the Traveling Salesman's Paths
Frans Schalekamp, András Sebő, Vera Traub +1
Gottschalk and Vygen proved that every solution of the subtour elimination linear program for traveling salesman paths is a convex combination of more and more restrictive "general…
The Salesman's Improved Paths: 3/2+1/34 Integrality Gap and Approximation Ratio
András Sebő, Anke van Zuylen
We give a new, strongly polynomial-time algorithm and improved analysis for the metric path TSP. It finds a tour of cost less than 1.53 times the optimum of the subtour elimi…
A Duality Based 2-Approximation Algorithm for Maximum Agreement Forest
Frans Schalekamp, Anke van Zuylen, Suzanne van der Ster
We give a 2-approximation algorithm for the Maximum Agreement Forest problem on two rooted binary trees. This NP-hard problem has been studied extensively in the past two decades,…
Improved Approximations for Cubic and Cubic Bipartite TSP
Anke van Zuylen
We show improved approximation guarantees for the traveling salesman problem on cubic graphs, and cubic bipartite graphs. For cubic bipartite graphs with n nodes, we improve on rec…
Scheduling over Scenarios on Two Machines
Esteban Feuerstein, Alberto Marchetti-Spaccamela, Frans Schalekamp +4
We consider scheduling problems over scenarios where the goal is to find a single assignment of the jobs to the machines which performs well over all possible scenarios. Each scena…
An Upper Bound on the Number of Circular Transpositions to Sort a Permutation
Anke van Zuylen, James Bieron, Frans Schalekamp +1
We consider the problem of upper bounding the number of circular transpositions needed to sort a permutation. It is well known that any permutation can be sorted using at most $n(n…