Computer Studies Bldg. Room 209
The Traveling Salesman Problem (TSP) is one of the best-known problems
in combinatorial optimization, with numerous applications. 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. This
can model, for example, minimizing the average waiting time of
customers located at the nodes. I present a new algorithm and
integrality gap bound for ATSPP and their use for designing an
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.
Refreshments will be provided at 10:45 AM