Matroid and Knapsack Center Problems

In the classic k-center problem, we are given a metric graph, and the objective is to select 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: (1) We consider the matroid center problem in which the centers are required to form an independent set of a given matroid. We show this problem is NP-hard even on a line. We present a 3-approximation algorithm for the problem on general metrics. We also consider the outlier version of the problem where a given number of vertices can be excluded as outliers from the solution. We present a 7-approximation for the outlier version. (2) We consider the (multi-)knapsack center problem in which the centers are required to satisfy one (or more) knapsack constraint(s). It is known that the knapsack center problem with a single knapsack constraint admits a 3-approximation. However, when there are at least two knapsack constraints, we show this problem is not approximable at all. To complement the hardness result, we present a polynomial time algorithm that gives a 3-approximate solution such that one knapsack constraint is satisfied and the others may be violated by at most a factor of \(1+\epsilon \). We also obtain a 3-approximation for the outlier version that may violate the knapsack constraint by \(1+\epsilon \).

1. Let \(B_1,B_2,\ldots , B_b\) be a collection of disjoint subsets of V and \(d_i\) be integers such that \(1\le d_i\le |B_i|\) for all \(1\le i\le b\). We say a set \(I\subseteq V\) is independent if \(|I\cap B_i|\le d_i\) for \(1\le i\le b\). All such independent sets form a partition matroid.

2. Note that this is the key difference between our charging argument and that of [2]; in [2], a node may be charged to some node far away.

3. We note that Golovin et al. [13] claimed (without a proof) that, in our notations, most existing approximation algorithms for k-median achieve an \(O(\lambda )\)-approximation on spaces satisfying \((\lambda ,2)\)-relaxed TI. By a scrutiny of the existing k-median algorithms, we are not able to reproduce the same result and the correct approximation ratio should be roughly \(O(\lambda ^{c_0})\). However, the results of [13] are not affected in any essential way since this only changes the constant hidden in the big-oh notation.

We would like to thank the anonymous reviewers for their insightful and detailed comments, which helped us to improve the presentation significantly.

Authors and Affiliations

1. Department of Computer Science and Engineering, University of Notre Dame, Notre Dame, IN, 46556, USA

   Danny Z. Chen

2. Institute for Interdisciplinary Information Sciences, Tsinghua University, Beijing, 100084, China

   Jian Li

3. Facebook, Inc., Seattle, WA, 98101, USA

   Hongyu Liang

4. Department of Computer Science, Utah State University, Logan, UT, 84322, USA

   Haitao Wang

Corresponding author

Correspondence to Jian Li.

A preliminary version of the paper appeared in the Proceedings of The 16th Conference on Integer Programming and Combinatorial Optimization (IPCO), 2013.

The research of D. Z. Chen was supported in part by NSF under Grant CCF-1217906.

Jian Li: Research supported in part by the National Basic Research Program of China Grants 2015CB358700, 2011CBA00300, 2011CBA00301, the National Natural Science Foundation of China Grants 61202009, 61033001, 61361136003.

This work was done when H. Liang was a student at Institute for Interdisciplinary Information Sciences, Tsinghua University, Beijing, China.

H. Wang’s research was supported in part by NSF under Grant CCF-1317143.

Appendix: A Constant Approximation for MatCenter

We say a space V with a distance function d satisfies the \((\lambda ,c)\) -relaxed triangle inequality (TI) for some \(\lambda \) and c, if \(d(a_0,a_c)\le \lambda \sum _{i=1}^{c}d(a_{i-1},a_i)\) for all \(a_0,a_1,\ldots ,a_c \in V\). (Thus a metric space satisfies the (1, c)-relaxed TI for all \(c\ge 1\).) By examining the algorithms in [3, 22] for the matroid median problem, we notice that they can actually achieve an approximation factor of \((\mu \lambda )\) for matroid median where \(\mu \) is some universal constant, if the underlying space satisfies the \((\lambda ,c_0)\)-relaxed TI for some algorithm-dependent \(c_0\).^{Footnote 3} (Roughly speaking, \(c_0\) is the maximum number of times that the triangle inequality is used for bounding the distance between a client and a facility.) Now, given an instance of MatCenter with metric space (V, d), we define a new distance function \(d'\) as \(d'(a,b)=(d(a,b))^p\) for all \(a,b\in V\), where \(p>2\) is a parameter whose value will be specified later. By the convexity of the function \(f(x)=x^{p}\) when \(p\ge 2\), for all \(c\ge 1\) and \(a_0,a_1,\ldots ,a_c \in V\), we have \((\sum _{i=1}^{c}d(a_{i-1},a_i)/c)^p \le \sum _{i=1}^{c}d(a_{i-1},a_i)^p/c\), and thus

Therefore \((V, d')\) satisfies the \((c^{p-1},c)\)-relaxed TI for all \(c \ge 1\). In particular, it satisfies the \((c_0^{p-1},c_0)\)-relaxed TI where \(c_0\) is the algorithm-dependent parameter mentioned before. We now solve the matroid median problem on the instance with the new distance function \(d'\). Let \(\mathsf {OPT}\) denote the optimal objective value of MatCenter on the original instance. Then it is clear that the optimal cost of matroid median on the new instance is at most \(|V|\cdot \mathsf {OPT}^{p}\). By our previous observation, the algorithms of [3, 22] give a solution of cost at most \(\mu c_0^{p-1}|V|\mathsf {OPT}^{p}\). Transforming the distance function back to d, the maximum service cost of any client is at most \((\mu c_0^{p-1}|V|\mathsf {OPT}^{p})^{1/p}=c_0^{1-1/p}(\mu |V|)^{1/p}\mathsf {OPT}\). By choosing \(p=\Omega (|V|)\), this can produce a \((c_0+\epsilon )\)-approximation for MatCenter for any fixed \(\epsilon >0\). Using the algorithm of [3] this roughly gives a 9-approximation.

Reprints and permissions