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.