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.