Fast Combinatorial Algorithms for Simultaneously Approximating All ℓ_p-Norms in Correlation Clustering

References

• [1] Ahmadi S, Khuller S, Saha B (2019) Min-max correlation clustering via multicut. Lodi A, Nagarajan V, eds. Integer Programming Combin. Optim. IPCO 2019, Lecture Notes in Computer Science, vol. 11480 (Springer, Cham, Switzerland), 13–26.Google Scholar
• [2] Ahmadi S, Galhotra S, Saha B, Schwartz R (2020) Fair correlation clustering. Preprint, submitted February 10, https://arxiv.org/abs/2002.03508.Google Scholar
• [3] Ahmadian S, Epasto A, Kumar R, Mahdian M (2020) Fair correlation clustering. Chiappa S, Calandra R, eds. Internat. Conf. Artificial Intelligence Statist., AISTATS 2020, Proceedings of Machine Learning Research, vol. 108 (PMLR, virtual), 4195–4205.Google Scholar
• [4] Ailon N, Charikar M, Newman A (2008) Aggregating inconsistent information: Ranking and clustering. J. ACM 55(5):1–27.Crossref, Google Scholar
• [5] Alamdari S, Shmoys D (2018) A bicriteria approximation algorithm for the k-center and k-median problems. Solis-Oba R, Fleischer R, eds. Approximation Online Algorithms. WAOA 2017, Lecture Notes in Computer Science, vol. 10787 (Springer, Cham, Switzerland), 66–75.Google Scholar
• [6] Azar Y, Epstein L, Richter Y, Woeginger GJ (2004) All-norm approximation algorithms. J. Algorithms 52(2):120–133.Crossref, Google Scholar
• [7] Bansal N, Blum A, Chawla S (2004) Correlation clustering. Machine Learn. 56(1):89–113.Crossref, Google Scholar
• [8] Bateni M, Cohen-Addad V, Epasto A, Lattanzi S (2022) Scalable and improved algorithms for individually fair clustering. Koyejo S, Mohamed S, Agarwal A, Belgrave D, Cho K, Oh A, eds. Workshop Trustworthy Soc. Responsible Machine Learn., Advances in Neural Information Processing Systems 35 (NeurIPS 2022, New Orleans, USA), 43646–43661.Google Scholar
• [9] Ben-Dor A, Yakhini Z (1999) Clustering gene expression patterns. Proc. 3rd Annual Internat. Conf. Comput. Molecular Biol. (Association for Computing Machinery, New York), 33–42.Google Scholar
• [10] Bernstein A, Kopelowitz T, Pettie S, Porat E, Stein C (2017) Simultaneously load balancing for every p-norm, with reassignments. 8th Innovations Theoret. Comput. Sci. Conf. (ITCS 2017) (Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Wadern, Germany), 51:1–51:14.Google Scholar
• [11] Bonchi F, Garcia-Soriano D, Liberty E (2014) Correlation clustering: From theory to practice. KDD’14: Proc. 20th ACM SIGKDD Internat. Conf. Knowledge Discovery Data Mining (Association for Computing Machinery, New York), 1972.Google Scholar
• [12] Cao N, Li S, Ye J (2024a) Simultaneously approximating all norms for massively parallel correlation clustering. Censor-Hillel K, Grandoni F, Ouaknine J, Puppis G, eds. 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025), Schloss Dagstuhl–Leibniz-Zentrum für Informatik, vol. 334 (Dagstuhl, Germany), 40:1–40:20.Google Scholar
• [13] Cao N, Cohen-Addad V, Lee E, Li S, Newman A, Vogl L (2024b) Understanding the cluster linear program for correlation clustering. Proc. 56th Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 1605–1616.Google Scholar
• [14] Chakrabarty S, Makarychev K (2023) Single-pass pivot algorithm for correlation clustering. Keep it simple! Preprint, submitted May 23, https://arxiv.org/abs/2305.13560.Google Scholar
• [15] Charikar M, Gupta N, Schwartz R (2017) Local guarantees in graph cuts and clustering. Eisenbrand F, Könemann J, eds. Integer Programming Combin. Optim. IPCO 2017, Lecture Notes in Computer Science, vol. 10328 (Springer, Cham, Switzerland), 136–147.Google Scholar
• [16] Charikar M, Guruswami V, Wirth A (2005) Clustering with qualitative information. J. Comput. System Sci. 71(3):360–383.Crossref, Google Scholar
• [17] Chatziafratis V, Gupta N, Lee E (2020) Inapproximability for local correlation clustering and dissimilarity hierarchical clustering. Preprint, submitted October 4, https://arxiv.org/abs/2010.01459.Google Scholar
• [18] Chawla S, Makarychev K, Schramm T, Yaroslavtsev G (2015) Near optimal LP rounding algorithm for correlation clustering on complete and complete k-partite graphs. Proc. 47th Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 219–228.Google Scholar
• [19] Chawla S, Krauthgamer R, Kumar R, Rabani Y, Sivakumar D (2006) On the hardness of approximating multicut and sparsest-cut. Comput. Complexity 15:94–114.Crossref, Google Scholar
• [20] Cheng Y, Church GM (2000) Biclustering of expression data. Bourne PE, Gribskov M, Altman RB, Jensen N, Hope D, Lengauer T, Mitchell JC, Scheeff J, Smith S, Strande S, Weissig H, eds. Proc. 8th Internat. Conf. Intelligent Systems Molecular Biol. (AAAI Press, Washington, DC), 93–103.Google Scholar
• [21] Chierichetti F, Dalvi N, Kumar R (2014) Correlation clustering in MapReduce. Proc. 20th ACM SIGKDD Internat. Conf. Knowledge Discovery Data Mining (Association for Computing Machinery, New York), 641–650.Google Scholar
• [22] Cohen MB, Lee YT, Song Z (2021) Solving linear programs in the current matrix multiplication time. J. ACM 68(1):1–39.Crossref, Google Scholar
• [23] Cohen-Addad V, Lee E, Newman A (2022) Correlation clustering with Sherali-Adams. 2022 IEEE Sympos. Foundations Comput. Sci. (FOCS) (IEEE, Piscataway, NJ), 651–661.Google Scholar
• [24] Cohen-Addad V, Lee E, Li S, Newman A (2023) Handling correlated rounding error via preclustering: A 1.73-approximation for correlation clustering. 64th IEEE Annual Sympos. Foundations Comput. Sci. (FOCS 2023) (IEEE, Piscataway, NJ), 1082–1104.Google Scholar
• [25] Cohen-Addad V, Lolck DR, Pilipczuk M, Thorup M, Yan S, Zhang H (2024) Combinatorial correlation clustering. Proc. 56th Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 1617–1628.Google Scholar
• [26] Davies S, Moseley B, Newman H (2023) Fast combinatorial algorithms for min max correlation clustering. Internat. Conf. Machine Learn. (PMLR).Google Scholar
• [27] Davies S, Moseley B, Newman H (2024) Simultaneously approximating all LP-norms in correlation clustering. 51st Internat. Colloquium Automata Languages Programming (ICALP 2024), Leibniz International Proceedings in Informatics (LIPIcs), vol. 297 (Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Wadern, Germany), 52:1–52:20.Google Scholar
• [28] Demaine ED, Immorlica N (2003) Correlation clustering with partial information. Arora S, Jansen K, Rolim JDP, Sahai A, eds. Approximation Randomization Combin. Optim. Algorithms Techniques, Random Approx 2003, Lecture Notes in Computer Science, vol. 2764 (Springer, Berlin, Heidelberg), 1–13.Crossref, Google Scholar
• [29] Demaine ED, Emanuel D, Fiat A, Immorlica N (2006) Correlation clustering in general weighted graphs. Theoret. Comput. Sci. 361(2–3):172–187.Crossref, Google Scholar
• [30] Friggstad Z, Mousavi R (2021) Fair correlation clustering with global and local guarantees. Lubiw A, Salavatipour M, He M, eds. Algorithms Data Structures. WADS 2021, Lecture Notes in Computer Science, vol. 12808 (Springer, Cham, Switzerland), 414–427.Google Scholar
• [31] Golovin D, Gupta A, Kumar A, Tangwongsan K (2008) All-norms and all-L_p-norms approximation algorithms. IARCS Annual Conf. Foundations Software Tech. Theoret. Comput. Sci., Leibniz International Proceedings in Informatics (LIPIcs), vol. 2 (Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Wadern, Germany), 199–210.Google Scholar
• [32] Gupta S, Moondra J, Singh M (2023) Which LP norm is the fairest? Approximations for fair facility location across all “p.” Proc. 24th ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 817.Google Scholar
• [33] Heidrich HS, Irmai J, Andres B (2024) A 4-approximation algorithm for min max correlation clustering. Dasgupta S, Mandt S, Li Y, eds. Internat. Conf. Artificial Intelligence Statist. AISTATS 2024 (PMLR, Valencia, Spain), 1945–1953.Google Scholar
• [34] Jafarov J, Kalhan S, Makarychev K, Makarychev Y (2021b) Local correlation clustering with asymmetric classification errors. Meila M, Zhang T, eds. Proc. 38th Internat. Conf. Machine Learn., ICML 2021, Proceedings of Machine Learning Research, vol. 139 (PMLR, virtual), 4677–4686.Google Scholar
• [35] Kalhan S, Makarychev K, Zhou T (2019) Correlation clustering with local objectives. Wallach HM, Larochelle H, Beygelzimer A, d’Alché-Buc F, Fox EB, Garnett R, eds. Proc. 33rd Internat. Conf. Neural Inform. Processing Systems (Curran Associates Inc., Red Hook, NY), 9341–9350.Google Scholar
• [36] Kleinberg J, Rabani Y, Tardos É (1999) Fairness in routing and load balancing. 40th Annual Sympos. Foundations Comput. Sci. (Cat. No. 99CB37039) (IEEE, Piscataway, NJ), 568–578.Google Scholar
• [37] Kriegel HP, Kröger P, Zimek A (2009) Clustering high-dimensional data: A survey on subspace clustering, pattern-based clustering, and correlation clustering. ACM Trans. Knowledge Discovery Data 3(1):1–58.Crossref, Google Scholar
• [38] Langley Z, Bernstein A, Assadi S (2020) Improved bounds for distributed load balancing. 34th Internat. Sympos. Distributed Comput. (DISC 2020), Leibniz International Proceedings Informatics (LIPIcs), vol. 179 (Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Wadern, Germany), 1:1–1:15.Google Scholar
• [39] McCallum A, Wellner B (2004) Conditional models of identity uncertainty with application to noun coreference. Saul LK, Weiss Y, Bottou L, eds. Proc. 18th Internat. Conf. Neural Inform. Processing Systems (Curran Associates Inc., Red Hook, NY), 905–912.Google Scholar
• [40] Pan X, Papailiopoulos D, Recht B, Ramchandran K, Jordan MI (2014) Scaling up correlation clustering through parallelism and concurrency control. Cortes C, Lawrence N, Lee D, Sugiyama M, Garnett R, eds. DISCML Workshop Internat. Conf. Neural Inform. Processing Systems (NIPS 2015, Montreal, Canada), 82–90.Google Scholar
• [41] Puleo GJ, Milenkovic O (2015) Correlation clustering with constrained cluster sizes and extended weights bounds. SIAM J. Optim. 25(3):1857–1872.Crossref, Google Scholar
• [42] Puleo GJ, Milenkovic O (2016) Correlation clustering and biclustering with locally bounded errors. Balcan M, Weinberger KQ, eds. Proc. 33rd Internat. Conf. Machine Learning, ICML 2016, JMLR Workshop and Conference Proceedings, vol. 48 (JMLR.org), 869–877.Google Scholar
• [43] Ruggles C, Veldt N, Gleich DF (2020) A parallel projection method for metric constrained optimization. 2020 Proc. SIAM Workshop Combin. Sci. Comput. (Society for Industrial and Applied Mathematics, Philadelphia), 43–53.Google Scholar
• [44] Shi J, Dhulipala L, Eisenstat D, Lacki J, Mirrokni VS (2021) Scalable community detection via parallel correlation clustering. Proc. VLDB Endowment 14(11):2305–2313.Crossref, Google Scholar
• [45] Sonthalia R, Gilbert AC (2022) Project and forget: Solving large-scale metric constrained problems. J. Machine Learn. Res. 23(326):1–54.Google Scholar
• [46] Symeonidis P, Nanopoulos A, Papadopoulos AN, Manolopoulos Y (2008) Nearest-biclusters collaborative filtering based on constant and coherent values. Inform. Retrieval 11(1):51–75.Crossref, Google Scholar
• [47] Veldt N (2022) Correlation clustering via strong triadic closure labeling: Fast approximation algorithms and practical lower bounds. Chaudhuri K, Jegelka S, Song L, Szepesvari C, Niu G, Sabato S, eds. Internat. Conf. Machine Learn., ICML 2022, Proceedings of Machine Learning Research, vol. 162 (PMLR, Baltimore), 22060–22083.Google Scholar
• [48] Veldt N, Gleich DF, Wirth A (2018) A correlation clustering framework for community detection. Proc. 2018 World Wide Web Conf. (International World Wide Web Conferences Steering Committee, Geneva), 439–448.Google Scholar
• [49] Veldt N, Gleich DF, Wirth A, Saunderson J (2019) Metric-constrained optimization for graph clustering algorithms. SIAM J. Math. Data Sci. 1(2):333–355.Crossref, Google Scholar
• [50] Wirth A (2017) Correlation clustering. Sammut C, Webb GI, eds. Encyclopedia of Machine Learning and Data Mining (Springer, Boston), 280–284.Crossref, Google Scholar