## 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**

**Abstract:**

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**

**Abstract:**

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**

**Abstract:**

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:

\begin{compactitem}[-]

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.

\end{compactitem}

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.