## 多色彩背包中心問題之探討 A Study on the Colorful Knapsack Center Problem

2021

Liang, Yi-Chang
##### Abstract
\$k\$中心問題是一個被廣泛研究的組合最佳化問題。本論文探討\$k\$中心與背包中心所衍生的新問題：多色彩背包中心問題。在多色彩背包中心問題中，我們給予一個含有多種彩色點的有限度量空間、 一個權重函數與一可用預算上限，還有各種顏色的覆蓋要求。目標是找出最小半徑\$ho\$，使得中心的總權重不大於預算下，各種顏色的覆蓋要求能被滿足。由於\$k\$中心問題是多色彩背包中心問題的特例，所以多色彩背包中心問題為NP困難問題。因此，對這個問題我們訴諸於尋找一個近似演算法。我們主要的結果為一個保證近似比率為\$3\$的類近似算法，固定一個參數\$epsilon> 0\$，保證使用的總預算的倍率在\$(1 + epsilon)\$以內。
The \$k\$-center problem is an extensively studied combinatorial optimization problem. In this thesis, we investigate an extension of the \$k\$-center problem and the knapsack center problem which is called the ``Colorful knapsack center problem". In the colorful knapsack center problem, we are given a set of colored points in a metric space, a weight function, a budget, and a coverage requirement for each color. The objective is to find the smallest radius \$ ho\$, such that the total weight of chosen centers does not exceed the budget, and the coverage requirement can be satisfied. The \$k\$-center problem is a special case of the colorful knapsack center problem, and thus the colorful knapsack center problem is NP-hard. Therefore, we resort to finding an efficient approximation algorithm for this problem. Our main result is a pseudo-approximation algorithm that guarantees the approximation ratio of \$3\$ where the knapsack constraint may be violated at most a factor of \$(1 + epsilon)\$ for any fixed \$epsilon> 0\$.