Monday, March 29, 2010
11:00 AM
Computer Studies Bldg. Room 209
Zoya Svitkina
University of Alberta
Asymmetric Traveling Salesman Path and Directed Latency Problems
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