Matroid and Knapsack Center Problems

Danny Z. Chen, Jian Li, Hongyu Liang, Haitao Wang

Abstract

In the classic k-center problem, we are given a metric graph, and the objective is to open k nodes as centers such that the maximum distance from any vertex to its closest center is minimized. In this paper, we consider two important generalizations of k-center, the matroid center problem and the knapsack center problem. Both problems are motivated by recent content distribution network applications. Our contributions can be summarized as follows:
BibTeX
@inproceedings{chen2013matroid,
  author = {Danny Z. Chen and Jian Li and Hongyu Liang and Haitao Wang},
  title = {{Matroid and Knapsack Center Problems}},
  booktitle = {IPCO},
  year = {2013},
  doi = {10.1007/978-3-642-36694-9\_10},
}

Loading related content...

Figure