University of Minnesota
University Relations
myU OneStop

Go to unit's home.

Home | Seminars and Symposia | Past seminars/symposia: Friday, April 29, 2005

DTC Seminar Series

How Well Can the 'Directed' Traveling Salesman Problem Be Approximated?


Howard Karloff Howard Karloff
ATT Labs — Research

Friday, April 29, 2005
10:00 am

402 Walter Library

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 polynomial-time algorithm known finds a tour whose length is at most O(log 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.


After receiving his PhD from Berkeley with Dick Karp, Howard Karloff taught at the University of Chicago and Georgia Tech before joining AT&T Labs—Research. An editor of ACM's Transactions on Algorithms, he has served on the program committees of numerous conferences and chaired the Symposium of Discrete Algorithms (SODA) program committee. He is the author of numerous journal and conference articles and the Birkhauser book "Linear Programming." His research interests span theoretical computer science but extend to more applied areas of computer science, such as networking, as well.