Abstract
In the classic $k$-center problem, the objective is to open $k$ nodes as centers in a metric graph to minimize the maximum distance from any vertex to its closest center. This paper investigates two significant generalizations: the matroid center problem and the knapsack center problem, both motivated by resource allocation in Content Distribution Networks (CDNs). We provide a 3-approximation algorithm for the matroid center problem and a 7-approximation for its outlier version. For the knapsack center problem, we demonstrate that while multiple constraints lead to inapproximability, a 3-approximation is achievable if slight budget violations are permitted.
Introduction
The $k$-center problem is a fundamental facility location problem. However, modern applications like CDNs often impose additional constraints on the set of chosen centers. For instance, different server types might be subject to independence constraints modeled by a matroid, or each potential location might have an associated cost subject to one or more knapsack budgets. This work explores the theoretical boundaries and algorithmic possibilities for these constrained versions of the $k$-center problem.
Hardness Results
A key contribution of this work is establishing the computational complexity of these variants. Surprisingly, the Matroid Center problem is NP-hard even when the metric space is restricted to a 1D line. This stands in stark contrast to the standard $k$-center problem, which is efficiently solvable in such simple metrics.
The hardness proof utilizes a reduction from 3-SAT, where specific gadgets are constructed to represent clauses, as shown in Figure 1. Furthermore, we prove that the multi-knapsack center problem with two or more constraints is completely inapproximable unless P=NP, meaning no constant-factor approximation exists without violating the constraints.
Algorithmic Approaches
To address these challenges, we propose several approximation algorithms based on combinatorial optimization and thresholding methods.
Matroid Center
We present the first 3-approximation algorithm for the matroid center problem on general metrics. The approach involves a greedy disk-covering strategy to form a partition matroid, followed by finding an intersection with the input matroid. For the "robust" version, which allows for a specified number of outliers, we provide a 7-approximation using a sophisticated charging argument to ensure coverage bounds are met.
Knapsack Center
While the multi-knapsack version is generally hard, we show that by allowing a violation of the budget constraints by a factor of $1+\epsilon$, we can recover a 3-approximation. This is achieved by reducing the problem to a group multi-knapsack problem and employing dynamic programming and scaling techniques. We also extend this to the outlier version, yielding a 3-approximation that violates the knapsack constraint by at most $1+\epsilon$.
Conclusion
This research clarifies the complexity landscape of constrained $k$-center problems. We provide the first constant-factor approximations for the matroid center problem and its robust variant. For knapsack constraints, we identify a sharp transition from approximability to inapproximability as the number of constraints increases, and provide a practical workaround via budget relaxation. Future work includes closing the approximation gaps and exploring robust versions with multiple constraints without budget violations.
Summary updated