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

Abstract:

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.

Biography:

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.