# Matroid and Knapsack Center Problems

Source: [Matroid and Knapsack Center Problems](<https://www.sota2.com/research/paper/68fa60c41e209131ce9f12ed>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-25T19:46:33.460Z

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

Published: 2013-01-04T15:17:06.000Z

## 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:   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 the 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$.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

- [Fair k-center on SushiB](<https://www.sota2.com/research/sota/fair-k-center-on-sushib.md>): Fair k-center; SushiB; Cost/LB Ratio (Gonzalez): 1.81.

- [Fair k-center on SushiA](<https://www.sota2.com/research/sota/fair-k-center-on-sushia.md>): Fair k-center; SushiA; Cost/Gonzalez LB Ratio: 2.13.

- [Fair k-center on Adult](<https://www.sota2.com/research/sota/fair-k-center-on-adult.md>): Fair k-center; Adult; Ratio Cost to LB: 2.04.

- [Fair k-center on CelebA](<https://www.sota2.com/research/sota/fair-k-center-on-celeba.md>): Fair k-center; CelebA; Cost Ratio: 1.9.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/1301.0745>)

[PDF](<https://arxiv.org/pdf/1301.0745.pdf>)
