Speaker: Viswanath Nagarajan
Title: The directed minimum latency problem
Abstract:
We study the directed latency problem: given an n-vertex asymmetric metric with
a root vertex r, find a spanning path originating at r that minimizes the sum
of latencies at all vertices (the latency of vertex v is the distance from r to
v along the path). This problem has been well-studied in symmetric metrics,
where the best known approximation ratio is 3.59. We give a quasi-polynomial
time algorithm for directed latency achieving approximation guarantee O(\rho
\log3 n) where \rho is the integrality gap of a natural LP-relaxation for
Asymmetric Traveling Salesman Path. The best bound we obtain is
\rho=O(\sqrt{n}), however we conjecture \rho=O(\log n).