Asymmetric Traveling Salesman Path and Directed Latency Problems
ABSTRACT:
The Traveling Salesman Problem (TSP) is one of the best-known NP-hard
problems in combinatorial optimization. In this talk I present recent work
that studies integrality gaps and approximability of two generalizations
of TSP on directed graphs. Given two specified nodes s and t, both
problems ask to find an s-t path visiting all other nodes.
In the asymmetric traveling salesman path problem (ATSPP), the objective
is to minimize the total cost of this path. In the directed latency
problem, the objective is to minimize the sum of distances on this path
from s to each node. I present a new algorithm for ATSPP that has
approximation ratio of O(log n), and whose analysis bounds the integrality
gap of the standard linear programming relaxation by the same factor. This
bound on the integrality gap for ATSPP is then used to obtain the second
major result, which is an O(log n)-approximation algorithm for the
directed latency problem.
BIO:
Zoya Svitkina has obtained a Bachelor of Science degree from the
University of Wisconsin - Madison, and a Ph.D. in Computer Science from
Cornell University, under the supervision of Prof. Eva Tardos.
She is currently a Postdoctoral Fellow at the University of Alberta in
Canada. Her research interests are in theoretical computer science,
combinatorial optimization, and approximation algorithms.