Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Phân cụm k-center màu sắc công bằng
Tóm tắt
Một trường hợp của k-center màu sắc gồm các điểm trong một không gian metric mà được tô màu đỏ hoặc xanh dương, cùng với một số nguyên k và yêu cầu phủ cho mỗi màu. Mục tiêu là tìm bán kính nhỏ nhất $$\rho $$ sao cho tồn tại các hình cầu bán kính $$\rho $$ xung quanh k điểm thỏa mãn các yêu cầu phủ. Động lực đằng sau vấn đề này có hai khía cạnh. Đầu tiên, từ góc độ công bằng: mỗi màu/group nên nhận được một đảm bảo dịch vụ tương tự, và thứ hai, từ những thách thức thuật toán mà nó đặt ra: vấn đề này kết hợp những khó khăn của phân cụm với bài toán tổng con. Cụ thể, chúng tôi chỉ ra rằng sự kết hợp này dẫn đến các giới hạn dưới mạnh mẽ về độ chênh lệch toàn bộ cho một số phương pháp lập trình tuyến tính tự nhiên. Kết quả chính của chúng tôi là một thuật toán xấp xỉ hiệu quả vượt qua những khó khăn này để đạt được một đảm bảo xấp xỉ là 3, gần khớp với đảm bảo xấp xỉ chặt chẽ là 2 cho bài toán k-center cổ điển mà vấn đề này tổng quát hóa. Các thuật toán trước đây đã mở ra nhiều hơn k trung tâm hoặc chỉ hoạt động trong trường hợp đặc biệt khi các điểm đầu vào nằm trong mặt phẳng.
Từ khóa
#k-center #phân cụm #lập trình tuyến tính #thuật toán xấp xỉ #không gian metricTài liệu tham khảo
Anagnostopoulos, A., Becchetti, L., Böhm, M., Fazzone, A., Leonardi, S., Menghini, C., Schwiegelshohn, C.: Principal fairness: removing bias via projections. CoRR arXiv:1905.13651 (2019)
Anegg, G., Angelidakis, H., Kurpisz, A., Zenklusen, R.: A technique for obtaining true approximations for k-center with covering constraints. In: International Conference on Integer Programming and Combinatorial Optimization (IPCO). pp. 52–65 (2020)
Arora, S., Ge, R.: New tools for graph coloring. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. pp. 1–12. Springer (2011)
Backurs, A., Indyk, P., Onak, K., Schieber, B., Vakilian, A., Wagner, T.: Scalable fair clustering. In: Proceedings of the 36th International Conference on Machine Learning, ICML. pp. 405–413 (2019)
Bandyapadhyay, S., Inamdar, T., Pai, S., Varadarajan, K.R.: A constant approximation for colorful k-center. In: 27th Annual European Symposium on Algorithms, ESA. pp. 1–14 (2019)
Chakrabarty, D., Goyal, P., Krishnaswamy, R.: The non-uniform k-center problem. In: 43rd International Colloquium on Automata, Languages, and Programming, ICALP. pp. 1–15 (2016)
Charikar, M., Khuller, S., Mount, D.M., Narasimhan, G.: Algorithms for facility location problems with outliers. In: Proceedings of the 12th Annual ACM-SIAM symposium on Discrete algorithms (SODA). pp. 642–651 (2001)
Chierichetti, F., Kumar, R., Lattanzi, S., Vassilvitskii, S.: Fair clustering through fairlets. In: Advances in Neural Information Processing Systems (NIPS). pp. 5029–5037 (2017)
Chlamtac, E., Friggstad, Z., Georgiou, K.: Understanding set cover: Sub-exponential time approximations and lift-and-project methods. CoRR arXiv:1204.5489 (2012)
Gonzalez, T.F.: Clustering to minimize the maximum intercluster distance. Theor. Comput. Sci. 38, 293–306 (1985)
Grigoriev, D.: Complexity of positivstellensatz proofs for the knapsack. Comput. Complex. 10(2), 139–154 (2001)
Harris, D.G., Pensyl, T., Srinivasan, A., Trinh, K.: A lottery model for center-type problems with outliers. ACM Trans. Algorithms 15(3), 1–25 (2019)
Hochbaum, D.S., Shmoys, D.B.: A best possible heuristic for the k-center problem. Math. Oper. Res. 10(2), 180–184 (1985)
Hsu, W.L., Nemhauser, G.L.: Easy and hard bottleneck location problems. Discret. Appl. Math. 1(3), 209–215 (1979)
Karlin, A.R., Mathieu, C., Nguyen, C.T.: Integrality gaps of linear and semi-definite programming relaxations for knapsack. In: Integer Programming and Combinatoral Optimization IPCO. pp. 301–314 (2011)
Lasserre, J.B.: An explicit exact SDP relaxation for nonlinear 0-1 programs. In: International Conference on Integer Programming and Combinatorial Optimization (IPCO). pp. 293–303 (2001)
Lasserre, J.B.: Global optimization with polynomials and the problem of moments. SIAM J. Optim. 11(3), 796–817 (2001)
Tulsiani, M.: CSP gaps and reductions in the lasserre hierarchy. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC. pp. 303–312 (2009)