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

[1] G. Anegg, H. Angelidakis, A. Kurpisz, and R. Zenklusen. A technique for obtaining true approximations for k-center with covering constraints. Mathematical Programming, pages 1–25, 2021.
[2] S. Bandyapadhyay, T. Inamdar, S. Pai, and K. Varadarajan. A constant approximation for colorful k-center. 27th Annual European Symposium on Algorithms, 2019.
[3] D. Bertsimas and J. N. Tsitsiklis. Introduction to linear optimization, volume 6.
[4] D. Chakrabarty, P. Goyal, and R. Krishnaswamy. The nonuniform k-center problem. ACM Transactions on Algorithms, 16(4):1–19, 2020.
[5] D. Chakrabarty and M. Negahbani. Generalized center problems with outliers. ACM Transactions on Algorithms, 15(3):1–14, 2019.
[6] M. Charikar, S. Khuller, D. M. Mount, and G. Narasimhan. Algorithms for facility location problems with outliers. In Proceedings of the 12th annual ACMSIAM symposium on Discrete algorithms, pages 642–651, 2001.
[7] D. Chen, J. Li, H. Liang, and H. Wang. Matroid and knapsack center problems. Algorithmica, 75(1):27–52, 2016.
[8] T. Feder and D. Greene. Optimal algorithms for approximate clustering. In Proceedings of the 12th annual ACM symposium on Theory of computing, pages 434–444, 1988.
[9] T. Gonzalez. Clustering to minimize the maximum intercluster distance. Theoretical computer science, 38:293–306, 1985.
[10] D. Harris, T. Pensyl, A. Srinivasan, and K. Trinh. A lottery model for center-type problems with outliers. ACM Transactions on Algorithms, 15(3):1–25, 2019.
[11] D. Hochbaum and D. Shmoys. A best possible heuristic for the k-center problem. Mathematics of operations research, 10(2):180–184, 1985.
[12] D. S. Hochbaum and D. B. Shmoys. A unified approach to approximation algorithms for bottleneck problems. Journal of the ACM, 33(3):533–550, 1986.
[13] W.L. Hsu and G. Nemhauser. Easy and hard bottleneck location problems. Discrete Applied Mathematics, 1(3):209–215, 1979.
[14] T. Inamdar. Covering and clustering with outliers and other constraints. PhD thesis, University of Iowa, 2020.
[15] X. Jia, K. Sheth, and O. Svensson. Fair colorful k-center clustering. Mathematical Programming, pages 1–22, 2021.
[16] N. Karmarkar. A new polynomial-time algorithm for linear programming. In Proceedings of the sixteenth annual ACM symposium on Theory of computing, pages 302–311, 1984.
[17] L. C. Lau, R. Ravi, and M. Singh. Iterative methods in combinatorial optimization, volume 46. Cambridge University Press, 2011. 51