Towards better approximation algorithms for classic combinatorial optimization problems

Tuesday, April 7, 2015 -
4:00pm to 5:00pm
CS 1240

Speaker Name: 

Shi Li

Speaker Institution: 

Toyota Technical Institute at Chicago

Cookies: 

Yes

Cookies Location: 

CS 1240

Description: 

Over the past three decades, approximation algorithm techniques have been successful in analyzing the approximability of many problems. However many other classic problems are still poorly-understood in terms of approximability. Long-standing gaps between approximation ratios and hardness of approximation results present challenges to our algorithmic techniques.

I will present two very different examples from my work to illustrate how various techniques were used to tackle long-standing gaps. The first example deals with the problem of connecting pairs of senders and receivers in a communication network with limited resources. A simple model is the edge-disjoint paths problem in which we need to connect as many pairs as possible using edge-disjoint paths. Despite many years of study, the best approximation ratio for this problem is only O(sqrt(n)). I will show how our work circumvented barriers for this problem by allowing a congestion 2 for the connections.

The second example deals with the classic k-median problem. Our work improved the previous decade-old (3+epsilon)-approximation algorithm. In particular, we show how allowing k+O(1) medians overcomes natural barriers, resulting in our improved approximation ratio.

Speaker bio: Shi Li obtained his Ph.D. from the Department of Computer Science at Princeton University, advised by Prof. Moses Charikar. Currently, he is a research assistant professor at Toyota Technological Institute at Chicago. Shi's research area is in theoretical computer science. Specifically, he is interested in designing and analyzing approximation algorithms for NP-hard combinatorial problems. Some problems he has worked on include facility location problems, network routing and design, scheduling, and resource allocation problems.