[Colloquium] Talks at TTIC: Shi Li, Princeton

[Liv Leader]

When:     Monday, February 11th @ 11 a.m.

Where:    TTIC, 6045 S. Kenwood Avenue, Room #526

Who:      Shi Li, Princeton

Title :     Approximation Algorithms for Facility Location and Network
Routing Problems

Abstract :

In this talk, I will talk about two broad themes of my research. The first
theme in my research is facility location problems. Two important problems
in this category are uncapacitated facility location and k-median. Both
problems have long histories and numerous applications. In the first part
of my talk, I will focus on my recent work with Svensson about an improved
approximation algorithm for k-median. Here, we are given a set of potential
facility locations and clients, with a distance function on these points.
The goal is to  open k facilities so as to minimize the sum of distances
from all clients  to their nearest open facilities. Our algorithm, which
gives a 1+sqrt(3)+eps-approximation for k-median, is based on two rather
surprising components. First, we show that in order to given an
alpha-approximation algorithm for k-median, it suffices to give a
pseudo-approximation algorithm that finds an alpha-approximate solution by
opening k+O(1) facilities. Second, we give such a pseudo-approximation
algorithm with alpha = 1+sqrt(3)+eps.

The second theme is network routing problems. These are an important class
of optimization problems, among which the Edge-Disjoint Paths (EDP) problem
is one of the central and most extensively studied. Here, we are given k
source-sink pairs in a network and want to connect as many pairs as
possible using edge-disjoint paths. In spite of its rich history, there is
still a huge gap between the sqrt(log n)-hardness of approximation and the
sqrt(n)-approximation ratio for the problem. In the second part of my talk,
I will give an overview of my joint work with Chuzhoy, which gives a
poly-logarithmic approximation for EDP by slightly relaxing the
edge-disjointness constraint : we allow each edge in the network to be used
twice (i.e, we allow congestion 2). This culminates a long line of research
on the EDP with congestion problem.

Host: Madhur Tulsiani, madhurt at ttic.edu

-- 
Liv Leader
Director of Human Resources and International Affairs

Toyota Technological Institute Chicago
6045 S Kenwood Ave
Chicago, IL 60637
Phone- (773) 702-5033
Fax-     (773) 834-9881
Email-  lleader at ttic.edu
Web-   www.ttic.edu
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20130206/b19eaea9/attachment.htm