Title: How Well Can the "Directed" Traveling Salesman Problem Be Approximated?
Speaker: Howard Karloff, AT & T Labs - Research
Date: September 20, 2004 3:30-4:30pm
Location: DIMACS Center, CoRE Bldg, Room 433, Rutgers University, Busch Campus, Piscataway, NJ
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.