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


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


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 cij ∈ {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


We consider the following single-machine scheduling problem, which is often denoted
1||∑ fj: we are given n jobs to be scheduled on a single machine, where each job j has an integral processing time pj, and there is a nondecreasing, nonnegative cost function fj(Cj) that specifies the cost of finishing j at time Cj; the objective is to minimize j=1n fj(Cj). 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.


  There are three major facts that should be watched out for in all payday loans in the United States. The main advantage of Viagra Soft Tablets comparing with other products of this type is its faster on-set effect.