Matroid and Knapsack Center Problems

Abstract

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$.

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$.³ (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

$$\begin{aligned} d'(a_0,a_c)= & {} d(a_0,a_c)^p \le \left( \sum _{i=1}^{c}d(a_{i-1},a_i)\right) ^{p} \\\le & {} c^{p-1}\sum _{i=1}^{c}d(a_{i-1},a_i)^p =c^{p-1}\sum _{i=1}^{c}d'(a_{i-1},a_i). \end{aligned}$$

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.