Center Problems under Matroid and Knapsack Constraints

Title: Center Problems under Matroid and Knapsack Constraints

Speaker: Hongyu Liang (Tsinghua University)

Time: 15:30-16:30, 18 June 2013

Venue: Lecture Room, 3rd Floor, Building #5, State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences

In the classical k-center problem, given a metric graph, we are required to designate k vertices as centers so as to minimize the

maximum distance from any vertex to its closest center. We initiate the study of two important generalizations of k-center, namely the

matroid center problem and the knapsack center problem, which replace the size constraint on the set of chosen centers with matroid or

knapsack constraints. Both problems are motivated by important applications in content distribution networks.  We give approximation

algorithms and hardness results for both problems. We also obtain approximation algorithms for the “robust” variant of the problems,

where a given number of vertices can be excluded as outliers from the solution. Finally, we will discuss some interesting open problems that

merit further investigation.

This is a joint work with Danny Chen, Jian Li, and Haitao Wang.

Dr. Hongyu Liang received his Ph.D. degree from the Institute for Interdisciplinary Information Sciences (IIIS), Tsinghua University in

2013, under the supervision of Prof. Andrew Yao. Before that, he got his B.E.  degree from Department of Computer Science and Technology,

Tsinghua University, in 2008.  His Ph.D. thesis focuses on the design and analysis of approximation algorithms for graph optimization

problems. He also did research in other areas including social networks, database theory, and circuit complexity.  He will join

Facebook, Inc. after graduation.