多色彩背包中心問題之探討

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