Invited Session Tue.2.H 3010

Tuesday, 13:15 - 14:45 h, Room: H 3010

Cluster 1: Approximation & online algorithms [...]

Travelling salesman problem I


Chair: Sylvia Boyd and David Shmoys



Tuesday, 13:15 - 13:40 h, Room: H 3010, Talk 1

Sylvia Boyd
The travelling salesman problem on cubic and subcubic graphs

Coauthors: René Sitters, Leen Stougie, Suzanne van der Ster


We study the travelling salesman problem (TSP) on the metric completion of cubic and subcubic graphs, which is known to be NP-hard. The problem
is of interest because of its relation to the famous 4⁄3 conjecture for metric TSP, which says that the integrality gap, i.e., the worst case
ratio between the optimal values of the TSP and its linear programming relaxation (the subtour elimination relaxation), is 4⁄3. We present the first algorithm for cubic graphs with approximation ratio 4⁄3. The proof uses polyhedral techniques in a surprising way, which is of independent interest. In fact we prove constructively that for any cubic graph on n vertices a tour of length 4n⁄3-2 exists, which also implies the 4⁄3 conjecture, as an upper bound, for this class of graph-TSP.



Tuesday, 13:45 - 14:10 h, Room: H 3010, Talk 2

Anke van Zuylen
A proof of the Boyd-Carr conjecture

Coauthors: Frans Schalekamp, David P. Williamson


Determining the precise integrality gap for the subtour LP relaxation of the traveling salesman problem is a significant open question, with little progress made in thirty years in the general case of symmetric costs that obey triangle inequality. Boyd and Carr observe that we do not even know the worst-case upper bound on the ratio of the optimal 2-matching to the subtour LP; they conjecture the ratio is at most 10⁄9.
In this paper, we prove the Boyd-Carr conjecture. In the case that a fractional 2-matching has no cut edge, we can further prove that an optimal 2-matching is at most 10⁄9 times the cost of the fractional 2-matching.



Tuesday, 14:15 - 14:40 h, Room: H 3010, Talk 3

András Sebő
Shorter tours by nicer ears

Coauthor: Jens Vygen


I will sketch some ideas leading us to a 7/5-approximation algorithm for the graphic TSP, a 3/2-approximation algorithm for the minimum connected T-join problem containing the graphic s-t-path TSP and a 4/3-approximation algorithm for the smallest 2-edge-connected spanning subgraph problem. The key ingredients are:

  • a special kind of ear-decomposition using matching theory (theorems of Lovász and Frank).
  • optimization of the used ear-decomposition using matroid intersection.
  • minmax theorems of these subjects transformed to linear programming weak duality.
    The last make possible to deduce lower bounds for the graphic TSP. These are necessary for proving the approximation ratio and the integrality gap of some associated linear programs.


  •   Payday Loans Illinois should not be obtained by people who do not have the capacity to repay the lenders. What makes Viagra Strips better than other forms of this medicine is its easiness of usage.