Abstract
In this paper, we investigate the min-max correlation clustering problem with outliers, which is a combination of the min-max correlation clustering problem with the robust clustering. We first prove that the problem is NP-hard to obtain any finite approximation algorithm. Then we design an approximation algorithm based on LP-rounding technique and receive a bi-criteria guarantee.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Ailon, N., Avigdor-Elgrabli, N., Liberty, E., Zuylen, A.V.: Improved approximation algorithms for bipartite correlation clustering. SIAM J. Comput. 41(5), 1110–1121 (2012)
Ailon, N., Charikar, M., Newman, A.: Aggregating inconsistent information: ranking and clustering. J. ACM 55(5), Article No. 23 (2008)
Bansal, N., Blum, A., Chawla, S.: Correlation clustering. Mach. Learn. 56(1–3), 89–113 (2004)
Bressan, M., Cesa-Bianchi, N., Paudice, A., Vitale, F.: Correlation clustering with adaptive similarity queries. In: Proceedings of NeurIPS, pp. 12510–12519 (2019)
Byrka, J., Fleszar, K., Rybicki, B., Spoerhase, J.: Bi-factor approximation algorithms for hard capacitated k-median problems. In: Proceedings of SODA, pp. 722–736 (2014)
Charikar, M., Gupta, N., Schwartz, R.: Local guarantees in graph cuts and clustering. In: Proceedings of IPCO, pp. 136–147 (2017)
Charikar, M., Guruswami, V., Wirth, A.: Clustering with qualitative information. J. Comput. Syst. Sci. 71(3), 360–383 (2005)
Chawla, S., Makarychev, K., Schramm, T., Yaroslavtsev, G.: 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 (2015)
Chehreghani, M.H.: Hierarchical correlation clustering and tree preserving embedding (2020). ArXiv preprint arXiv: 2002.07756
Fukunaga, T.: LP-based pivoting algorithm for higher-order correlation clustering. J. Comb. Optim. 37(4), 1312–1326 (2018). https://doi.org/10.1007/s10878-018-0354-y
Giotis, I., Guruswami, V.: Correlation clustering with a fixed number of clusters. In: Proceedings of SODA, pp. 1167–1176 (2006)
Hou, J.P., Emad, A., Puleo, G.J., Ma, J., Milenkovic, O.: A new correlation clustering method for cancer mutation analysis. Bioinformatics 32(24), 3717–3728 (2016)
Jafarov, J., Kalhan, S., Makarychev, K., Makarychev, Y.: Correlation clustering with asymmetric classification errors. In: Proceedings of ICML, pp. 4641–4650 (2020)
Kim, S., Yoo, C.D., Nowozin, S., Kohli, P.: Image segmentation using higher-order correlation clustering. IEEE Trans. Pattern Anal. Mach. Intell. 36(9), 1761–1774 (2014)
Krishnaswamy, R., Rajaraman, N.: Robust correlation clustering. In: Proceedings of APPROX/RANDOM, pp. 33:1–33:18 (2019)
Lange, J.H., Karrenbauer, A., Andres, B.: Partial optimality and fast lower bounds for weighted correlation clustering. In: Proceedings of ICML, pp. 2892–2901 (2018)
Li, P., Puleo, G.J., Milenkovic, O.: Motif and hypergraph correlation clustering. IEEE Trans. Inf. Theory 66(5), 3065–3078 (2019)
Lv, W., Wu, C.: An LP-rounding based algorithm for a capacitated uniform facility location problem with penalties. J. Comb. Optim. 41(4), 888–904 (2021). https://doi.org/10.1007/s10878-021-00726-0
Makarychev, K., Makarychev, Y., Vijayaraghavan, A.: Correlation clustering with noisy partial information. In: Proceedings of COLT, pp. 1321–1342 (2015)
Mathieu, C., Schudy, W.: Correlation clustering with noisy input. In: Proceedings of SODA, pp. 712–728 (2010)
Puleo, G.J., Milenkovic, O.: Correlation clustering and biclustering with locally bounded errors. IEEE Trans. Inf. Theory 64(6), 4105–4119 (2018)
Saif, A., Delage, E.: Data-driven distributionally robust capacitated facility location problem. Eur. J. Oper. Res. 291(3), 995–1007 (2021)
Thiel, E., Chehreghani, M.H., Dubhashi, D.: A non-convex optimization approach to correlation clustering. In: Proceedings of AAAI, pp. 5159–5166 (2019)
Ukkonen, A.: Crowdsourced correlation clustering with relative distance comparisons. In: Proceedings of ICDM, pp. 1117–1122 (2017)
Vainstein, D., Chatziafratis, V., Citovsky, G., Rajagopalan, A., Mahdian, M., Azar, Y.: Hierarchical clustering via sketches and hierarchical correlation clustering (2021). ArXiv preprint arXiv: 2101.10639
Vasilyev, I., Ushakov, A.V., Maltugueva, N., Sforza, A.: An effective heuristic for large-scale fault-tolerant k-median problem. Soft Comput. 23(9), 2959–2967 (2019)
Veldt, N., Gleich, D.F., Wirth, A.: A correlation clustering framework for community detection. In: Proceedings of WWW, pp. 439–448 (2018)
Acknowledgements
The first author is supported by National Natural Science Foundation of China (No. 12101594) and the Project funded by China Postdoctoral Science Foundation (No. 2021M693337). The second author is supported by Natural Science Foundation of Shandong Province (No. ZR2020MA029) of China. The third author is supported by Beijing Natural Science Foundation (No. Z200002). The fourth author is supported by Nationa Natural Science Foundation of China (Nos. 12131003, 12001025).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Ji, S., Li, M., Liang, M., Zhang, Z. (2021). Approximation Algorithm for Min-Max Correlation Clustering Problem with Outliers. In: Du, DZ., Du, D., Wu, C., Xu, D. (eds) Combinatorial Optimization and Applications. COCOA 2021. Lecture Notes in Computer Science(), vol 13135. Springer, Cham. https://doi.org/10.1007/978-3-030-92681-6_52
Download citation
DOI: https://doi.org/10.1007/978-3-030-92681-6_52
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-92680-9
Online ISBN: 978-3-030-92681-6
eBook Packages: Computer ScienceComputer Science (R0)