Title:  How Well Can the *Directed* Traveling Salesman Problem Be Approximated?
Speaker:   Howard Karloff, ATT Labs--Research

Details: Monday, Sept 20, 3.30 to 4.30 PM, Core 433.

Abstract:
We study the version of the classic traveling salesman
problem (TSP) in which the distance from s to t can differ from the
distance from t to s (perhaps because of the presence
of one-way roads).  In such a case, the best poly-time algorithm known
finds a tour whose length is at most 
(log_2 n) times the length of the optimal tour, n being the number of cities.   

However, there is a 30+ year old linear programming-based technique
for bounding the cost of the optimal solution from below.  Until
recently, it was conjectured by some to be within a factor of 4/3
of the optimal cost, leading to hope that it could be the basis
for an algorithm producing a tour of cost at most 4/3 times optimal.

We prove that the conjecture is false:  No such 4/3-approximation algorithm,
based on the given relaxation, is possible.  In fact, no such 
1.999-approximation algorithm exists, either.  

---
This is joint work with Moses Charikar of Princeton and Michel Goemans of MIT.