Tuesday, January 19

Session 44
The TSP and Postman Problem

3:00 PM-4:00 PM
Room: Liberty B
Chair: Leslie Hall, Johns Hopkins University

3:00-3:17 Approximation Algorithms for the Asymmetric Postman Problem

Balaji Raghavachari, University of Texas at Dallas, Richardson; and Jeyakesavan Veerasamy, University of Texas at Dallas, Richardson and Samsung Telecommunications America, Inc.

3:20-3:37 Simplicity and Hardness of the Maximum Traveling Salesman Problem Under Geometric Distances

Sándor P. Fekete, Universität zu Köln, Germany

3:40-3:57 A Convex Relaxation for the Asymmetric Traveling Salesman Problem

Santosh Vempala, Massachusetts Institute of Technology; and Mihalis Yannakakis, Bell Laboratories, Lucent Technologies

SODA'99 Home

Program

Program Updates

Author Index

Hotel

Transportation

Registration

TJF, 9/14/98, MMD, 10/14/98