Approximation algorithms for the capacitated correlation clustering problem with penalties. (English) Zbl 1507.90146
Summary: This paper considers the capacitated correlation clustering problem with penalties (CCorCwP), which is a new generalization of the correlation clustering problem. In this problem, we are given a complete graph, each edge is either positive or negative. Moreover, there is an upper bound on the number of vertices in each cluster, and each vertex has a penalty cost. The goal is to penalize some vertices and select a clustering of the remain vertices, so as to minimize the sum of the number of positive cut edges, the number of negative non-cut edges and the penalty costs. In this paper we present an integer programming, linear programming relaxation and two polynomial time algorithms for the CCorCwP. Given parameter \(\delta \in (0,4/9]\), the first algorithm is a \(\left( 8/(4-5\delta), 8/\delta \right)\)-bi-criteria approximation algorithm for the CCorCPwP, which means that the number of vertices in each cluster does not exceed \(8/(4-5\delta)\) times the upper bound, and the output objective function value of the algorithm does not exceed \(8/\delta\) times the optimal value. The second one is based on above bi-criteria approximation, and we prove that the second algorithm can achieve a constant approximation ratio for some special instances of the CCorCwP.
MSC:
| 90C27 | Combinatorial optimization |
| 90C59 | Approximation methods and heuristics in mathematical programming |
References:
| [1] | Aboud A, Rabani Y (2008) Correlation clustering with penalties and approximating the reordering buffer management problem. Doctoral dissertation, Computer Science Department, Technion |
| [2] | Ahmadi S, Khuller S, Saha B (2019) Min-max correlation clustering via multicut. In: Proceedings of the 20th international conference on integer programming and combinatorial optimization, pp 13-26 · Zbl 1436.90114 |
| [3] | Ahn KJ, Cormode G, Guha S, Mcgregor A, Wirth A (2015) Correlation clustering in data streams. In: Proceedings of the 32nd international conference on machine learning, pp 2237-2246 · Zbl 1515.68281 |
| [4] | Ailon, N.; Avigdor-Elgrabli, N.; Liberty, E.; Zuylen, AV, Improved approximation algorithms for bipartite correlation clustering, SIAM J Comput, 41, 5, 1110-1121 (2012) · Zbl 1257.68076 · doi:10.1137/110848712 |
| [5] | Bansal, N.; Blum, A.; Chawla, S., Correlation clustering, Mach Learn, 56, 1-3, 89-113 (2004) · Zbl 1089.68085 · doi:10.1023/B:MACH.0000033116.57574.95 |
| [6] | Bressan M, Cesa-Bianchi N, Paudice A, Vitale F (2019) Correlation clustering with adaptive similarity queries. In: Proceedings of the 32nd annual conference on neural information processing systems, pp 12510-12519 |
| [7] | Castro, J.; Nasini, S.; Saldanha-Da-Gama, F., A cutting-plane approach for large-scale capacitated multi-period facility location using a specialized interior-point method, Math Program, 163, 1-2, 411-444 (2017) · Zbl 1365.90169 · doi:10.1007/s10107-016-1067-6 |
| [8] | Charikar, M.; Guruswami, V.; Wirth, A., Clustering with qualitative information, J Comput Syst Sci, 3, 71, 360-383 (2005) · Zbl 1094.68075 · doi:10.1016/j.jcss.2004.10.012 |
| [9] | Chawla S, Makarychev K, Schramm T, Yaroslavtsev G (2015) Near optimal LP rounding algorithm for correlation clustering on complete and complete \(k\)-partite graphs. In: Proceedings of the 47th ACM symposium on theory of computing, pp 219-228 · Zbl 1321.68495 |
| [10] | Chen X, Hu X, Jia X, Li M, Tang Z, Wang C (2018) Mechanism design for two-opposite-facility location games with penalties on distance. In: Proceedings of the 10th international symposium on algorithmic game theory, pp 256-260 · Zbl 1415.91066 |
| [11] | Cohen-Addad V (2020) Approximation schemes for capacitated clustering in doubling metrics. In: Proceedings of the 30th annual ACM-SIAM symposium on discrete algorithms, pp 2241-2259 · Zbl 07304162 |
| [12] | Filippi, C.; Guastaroba, G.; Speranza, MG, On single-source capacitated facility location with cost and fairness objectives, Eur J Oper Res, 289, 3, 959-974 (2021) · Zbl 1487.90436 · doi:10.1016/j.ejor.2019.07.045 |
| [13] | Jafarov J, Kalhan S, Makarychev K, Makarychev Y (2020) Correlation clustering with asymmetric classification errors. In: Proceedings of the 37th international conference on machine learning, pp 4641-4650 |
| [14] | Ji S, Cheng Y, Tan J, Zhao Z (2021) An improved approximation algorithm for capacitated correlation clustering problem. In: Proceedings of the 15th annual international conference on combinatorial optimization and applications, pp 35-45 · Zbl 07550512 |
| [15] | Ji, S.; Xu, D.; Du, D.; Wu, C., Approximation algorithms for the fault-tolerant facility location problem with penalties, Discret Appl Math, 264, 62-75 (2019) · Zbl 1418.90139 · doi:10.1016/j.dam.2019.01.003 |
| [16] | Lange JH, Karrenbauer A, Andres B (2018) Partial optimality and fast lower bounds for weighted correlation clustering. In: Proceedings of the 35th international conference on international conference on machine learning, pp 2892-2901 |
| [17] | Li, P.; Puleo, GJ; Milenkovic, O., Motif and hypergraph correlation clustering, IEEE Trans Inf Theory, 66, 5, 3065-3078 (2019) · Zbl 1448.05150 · doi:10.1109/TIT.2019.2940246 |
| [18] | Puleo, GJ; Milenkovic, O., Correlation clustering with constrained cluster sizes and extended weights bounds, SIAM J Optim, 25, 3, 1857-1872 (2015) · Zbl 1337.68296 · doi:10.1137/140994198 |
| [19] | Thiel E, Chehreghani MH, Dubhashi D (2019) A non-convex optimization approach to correlation clustering. In: Proceedings of the 33rd AAAI conference on artificial intelligence, pp 5159-5166 |
| [20] | Xu, Y.; Möhring, RH; Xu, D.; Zhang, Y.; Zou, Y., A constant FPT approximation algorithm for hard-capacitated \(k\)-means, Optim Eng, 21, 2, 709-722 (2020) · Zbl 1457.90138 · doi:10.1007/s11081-020-09503-0 |
| [21] | Zhang, D.; Hao, C.; Wu, C.; Xu, D.; Zhang, Z., Local search approximation algorithms for the \(k\)-means problem with penalties, J Comb Optim, 37, 2, 439-453 (2019) · Zbl 1420.90079 · doi:10.1007/s10878-018-0278-6 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
