## Invited Session Mon.1.H 3010

#### Monday, 10:30 - 12:00 h, Room: H 3010

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

### Approximation in routing and others

**Chair: Sylvia Boyd and David Shmoys**

**Monday, 10:30 - 10:55 h, Room: H 3010, Talk 1**

**Hyung-Chan An**

Improving Christofides' algorithm for the *s-t* path TSP

**Coauthors: Robert Kleinberg, David B. Shmoys**

**Abstract:**

We present a deterministic *\frac{1+√5 }{2}*-approximation algorithm for the *s*-*t* path TSP for an arbitrary metric. Given a symmetric metric cost on *n* vertices including two prespecified endpoints, the problem is to find a shortest Hamiltonian path between the two endpoints; Hoogeveen showed that the natural variant of Christofides' algorithm is a *5/3*-approximation algorithm for this problem, and this asymptotically tight bound in fact had been the best approximation ratio known until now. We modify this algorithm so that it chooses the initial spanning tree based on an optimal solution to the Held-Karp relaxation rather than a minimum spanning tree; we prove this simple but crucial modification leads to an improved approximation ratio, surpassing the 20-year-old barrier set by the natural Christofides' algorithm variant. Our algorithm also proves an upper bound of *\frac{1+√5 }{2}* on the integrality gap of the path-variant Held-Karp relaxation. The techniques devised in this paper can be applied to other optimization problems as well, including the prize-collecting *s*-*t* path problem and the unit-weight graphical metric *s*-*t* path TSP.

**Monday, 11:00 - 11:25 h, Room: H 3010, Talk 2**

**Frans Schalekamp**

On the integrality gap of the subtour LP for the 1,2-TSP

**Coauthors: Jiawei Qian, Anke van Zuylen, David P. Williamson**

**Abstract:**

We study the integrality gap of the subtour LP relaxation for the traveling salesman problem in the special case when all edge costs are either *1* or *2*. For the general case of symmetric costs that obey triangle inequality, a famous conjecture is that the integrality gap is *4⁄3*. Little progress towards resolving this conjecture has been made in thirty years, even though there has very recently been exciting progress with new approximation algorithms for special cases of the TSP, as well as for some related problems.

We conjecture that when all edge costs *c*_{ij} ∈ {1,2}, the integrality gap is *10⁄9*. We show that this conjecture is true when the optimal subtour LP solution has a certain structure. Under a weaker assumption, which is an analog of a recent conjecture by Schalekamp, Williamson and van Zuylen, we show that the integrality gap is at most *7⁄6*. When we do not make any assumptions on the structure of the optimal subtour LP solution, we can show that inegrality gap is at most *19⁄15≈ 1.267 < 4/3*; this is the first bound on the integrality gap of the subtour LP strictly less than *4/3* known for an interesting special case of the TSP.

**Monday, 11:30 - 11:55 h, Room: H 3010, Talk 3**

**David Shmoys**

A primal-dual approximation algorithm for min-sum single-machine scheduling problems

**Coauthor: Maurice Cheung**

**Abstract:**

We consider the following single-machine scheduling problem, which is often denoted

*1||∑ f*_{j}: we are given *n* jobs to be scheduled on a single machine, where each job *j* has an integral processing time *p*_{j}, and there is a nondecreasing, nonnegative cost function *f*_{j}(C_{j}) that specifies the cost of finishing *j* at time *C*_{j}; the objective is to minimize *∑*_{j=1}^{n} f_{j}(C_{j}). Bansal & Pruhs recently gave the first constant approximation algorithm and we improve on their *16*-approximation algorithm, by giving a primal-dual pseudo-polynomial-time algorithm that finds a solution of cost at most twice the optimal cost,

and then show how this can be extended to yield, for any *ε >0*, a *(2+ε)*-approximation algorithm for this problem. Furthermore, we generalize this result to allow the machine's speed to vary over time arbitrarily, for which no previous constant-factor approximation algorithm was known.