### DIMACS Theoretical Computer Science Seminar

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.