research-article

Near Optimal LP Rounding Algorithm for CorrelationClustering on Complete and Complete k-partite Graphs

Authors:

Konstantin Makarychev,

Tselil Schramm,

Grigory YaroslavtsevAuthors Info & Claims

STOC '15: Proceedings of the forty-seventh annual ACM symposium on Theory of Computing

Pages 219 - 228

https://doi.org/10.1145/2746539.2746604

Published: 14 June 2015 Publication History

Abstract

We give new rounding schemes for the standard linear programming relaxation of the correlation clustering problem, achieving approximation factors almost matching the integrality gaps: For complete graphs our approximation is 2.06 - ε, which almost matches the previously known integrality gap of 2. For complete k-partite graphs our approximation is 3. We also show a matching integrality gap. For complete graphs with edge weights satisfying triangle inequalities and probability constraints, our approximation is 1.5, and we show an integrality gap of 1.2.

Our results improve a long line of work on approximation algorithms for correlation clustering in complete graphs, previously culminating in a ratio of 2.5 for the complete case by Ailon, Charikar and Newman (JACM'08). In the weighted complete case satisfying triangle inequalities and probability constraints, the same authors give a 2-approximation; for the bipartite case, Ailon, Avigdor-Elgrabli, Liberty and van Zuylen give a 4-approximation (SICOMP'12).

References

[1]

N. Ailon. Aggregation of partial rankings, p-ratings and top-m lists. Algorithmica, 57(2):284--300, 2010.

Digital Library

[2]

N. Ailon, N. Avigdor-Elgrabli, E. Liberty, and A. van Zuylen. Improved approximation algorithms for bipartite correlation clustering. SIAM J. Comput., 41(5):1110--1121, 2012.

Digital Library

[3]

N. Ailon, M. Charikar, and A. Newman. Aggregating inconsistent information: Ranking and clustering. J. ACM, 55(5), 2008.

Digital Library

[4]

N. Ailon and E. Liberty. Correlation clustering revisited: The "true" cost of error minimization problems. In Proceedings of the 36th International Colloquium on Automata, Languages and Programming: Part I, ICALP '09, pages 24--36, Berlin, Heidelberg, 2009. Springer-Verlag.

Digital Library

[5]

N. Amit. The bicluster graph editing problem. PhD thesis, Tel Aviv University, 2004.

[6]

N. Bansal, A. Blum, and S. Chawla. Correlation clustering. Machine Learning, 56(1--3):89--113, 2004.

Digital Library

[7]

A. Ben-Dor, R. Shamir, and Z. Yakhini. Clustering gene expression patterns. Journal of Computational Biology, 6(3--4):281--297, 2014/11/02 1999.

[8]

M. Charikar, V. Guruswami, and A. Wirth. Clustering with qualitative information. J. Comput. Syst. Sci., 71(3):360--383, 2005.

Digital Library

[9]

S. Chawla, R. Krauthgamer, R. Kumar, Y. Rabani, and D. Sivakumar. On the hardness of approximating multicut and sparsest-cut. computational complexity, 15(2):94--114, 2006.

Digital Library

[10]

Y. Chen, S. Sanghavi, and H. Xu. Clustering sparse graphs. In F. Pereira, C. Burges, L. Bottou, and K. Weinberger, editors, Advances in Neural Information Processing Systems 25, pages 2204--2212. Curran Associates, Inc., 2012.

[11]

F. Chierichetti, N. N. Dalvi, and R. Kumar. Correlation clustering in mapreduce. In The 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '14, New York, NY, USA - August 24 - 27, 2014, pages 641--650, 2014.

Digital Library

[12]

W. Cohen and J. Richman. Learning to match and cluster entity names. In In ACM SIGIR-2001 Workshop on Mathematical/Formal Methods in Information Retrieval, 2001.

[13]

W. W. Cohen and J. Richman. Learning to match and cluster large high-dimensional data sets for data integration. In Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '02, pages 475--480, New York, NY, USA, 2002. ACM.

Digital Library

[14]

E. D. Demaine, D. Emanuel, A. Fiat, and N. Immorlica. Correlation clustering in general weighted graphs. Theor. Comput. Sci., 361(2--3):172--187, 2006.

Digital Library

[15]

N. Downing, P. J. Stuckey, and A. Wirth. Improved consensus clustering via linear programming. In Computer Science 2010, Thirty-Third Australasian Computer Science Conference (ACSC 2010), Brisbane, Australia, January 18--22, 2010, Proceedings, pages 61--70, 2010.

Digital Library

[16]

V. Filkov. Integrating microarray data by consensus clustering. In In Proceedings of International Conference on Tools with Artificial Intelligence (ICTAI, pages 418--425, 2003.

Digital Library

[17]

A. Gionis, H. Mannila, and P. Tsaparas. Clustering aggregation. TKDD, 1(1), 2007.

Digital Library

[18]

I. Giotis and V. Guruswami. Correlation clustering with a fixed number of clusters. In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm, SODA '06, pages 1167--1176, Philadelphia, PA, USA, 2006. Society for Industrial and Applied Mathematics.

Digital Library

[19]

M. Karpinski and W. Schudy. Linear time approximation schemes for the gale-berlekamp game and related minimization problems. In Proceedings of the Forty-first Annual ACM Symposium on Theory of Computing, STOC '09, pages 313--322, New York, NY, USA, 2009. ACM.

Digital Library

[20]

K. Makarychev, Y. Makarychev, and A. Vijayaraghavan. Algorithms for semi-random correlation clustering. arXiv preprint arXiv:1406.5667, 2014.

[21]

C. Mathieu, O. Sankur, and W. Schudy. Online Correlation Clustering. In J.-Y. Marion and T. Schwentick, editors, 27th International Symposium on Theoretical Aspects of Computer Science, volume 5 of Leibniz International Proceedings in Informatics (LIPIcs), pages 573--584, Dagstuhl, Germany, 2010. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik.

[22]

C. Mathieu and W. Schudy. Correlation clustering with noisy input. In Proceedings of the Twenty-first Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '10, pages 712--728, Philadelphia, PA, USA, 2010. Society for Industrial and Applied Mathematics.

Digital Library

[23]

A. Mccallum and B. Wellner. Toward conditional models of identity uncertainty with application to proper noun coreference. In In NIPS, pages 905--912. MIT Press, 2003.

[24]

C. Swamy. Correlation clustering: Maximizing agreements via semidefinite programming. In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '04, pages 526--527, Philadelphia, PA, USA, 2004. Society for Industrial and Applied Mathematics.

Digital Library

[25]

J. Tan. A note on the inapproximability of correlation clustering. Inf. Process. Lett., 108(5):331--335, Nov. 2008.

Digital Library

[26]

J. Van Gael and X. Zhu. Correlation clustering for crosslingual link detection. In Proceedings of the 20th International Joint Conference on Artifical Intelligence, IJCAI'07, pages 1744--1749, San Francisco, CA, USA, 2007. Morgan Kaufmann Publishers Inc.

Digital Library

[27]

A. van Zuylen, R. Hegde, K. Jain, and D. P. Williamson. Deterministic pivoting algorithms for constrained ranking and clustering problems. In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, New Orleans, Louisiana, USA, January 7--9, 2007, pages 405--414, 2007.

Digital Library

[28]

D. P. Williamson and D. B. Shmoys. The Design of Approximation Algorithms. Cambridge University Press, 2011.

[29]

A. Wirth. Correlation clustering. In C. Sammut and G. Webb, editors, Encyclopedia of Machine Learning, pages 227--231. Springer US, 2010.

Cited By

Ji SLi MLiang MZhang Z(2024)Robust Correlation Clustering Problem with Locally Bounded DisagreementsTsinghua Science and Technology10.26599/TST.2023.901002729:1(66-75)Online publication date: Feb-2024
https://doi.org/10.26599/TST.2023.9010027
Cohen-Addad VDas DKipouridis EParotsidis NThorup M(2024)Fitting Distances by Tree Metrics Minimizing the Total Error within a Constant FactorJournal of the ACM10.1145/3639453Online publication date: 2-Jan-2024
https://doi.org/10.1145/3639453
Ostovari MZarei A(2024)A Better LP Rounding for Feedback Arc Set on TournamentsTheoretical Computer Science10.1016/j.tcs.2024.114768(114768)Online publication date: Aug-2024
https://doi.org/10.1016/j.tcs.2024.114768
Show More Cited By

Index Terms

Near Optimal LP Rounding Algorithm for CorrelationClustering on Complete and Complete k-partite Graphs
1. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

A near-optimal approximation algorithm for Asymmetric TSP on embedded graphs
SOCG'14: Proceedings of the thirtieth annual symposium on Computational geometry

We present a near-optimal polynomial-time approximation algorithm for the asymmetric traveling salesman problem for graphs of bounded orientable or non-orientable genus. Given any algorithm that achieves an approximation ratio of f(n) on arbitrary n-...
Near-Optimal Distributed Dominating Set in Bounded Arboricity Graphs
PODC'22: Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing

We describe a simple deterministic O(ε-1 log Δ) round distributed algorithm for (2α+ 1) (1 + ε) approximation of minimum weighted dominating set on graphs with arboricity at most α. Here Δ denotes the maximum degree. We also show a lower bound proving ...
Spanners of Complete $k$-Partite Geometric Graphs

We address the following problem: Given a complete $k$-partite geometric graph $K$ whose vertex set is a set of $n$ points in $\mathbb{R}^d$, compute a spanner of $K$ that has a “small” stretch factor and “few” edges. We present two algorithms for this ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '15: Proceedings of the forty-seventh annual ACM symposium on Theory of Computing

June 2015

916 pages

ISBN:9781450335362

DOI:10.1145/2746539

General Chair:
Rocco Servedio
Columbia University
,
Program Chair:
Ronitt Rubinfeld
MIT and Tel Aviv University

Copyright © 2015 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 June 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National Science Foundation

Conference

STOC '15

Sponsor:

SIGACT

STOC '15: Symposium on Theory of Computing

June 14 - 17, 2015

Oregon, Portland, USA

Acceptance Rates

STOC '15 Paper Acceptance Rate 93 of 347 submissions, 27%;

Overall Acceptance Rate 716 of 2,233 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

42
Total Citations
View Citations
440
Total Downloads

Downloads (Last 12 months)56
Downloads (Last 6 weeks)7

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ji SLi MLiang MZhang Z(2024)Robust Correlation Clustering Problem with Locally Bounded DisagreementsTsinghua Science and Technology10.26599/TST.2023.901002729:1(66-75)Online publication date: Feb-2024
https://doi.org/10.26599/TST.2023.9010027
Cohen-Addad VDas DKipouridis EParotsidis NThorup M(2024)Fitting Distances by Tree Metrics Minimizing the Total Error within a Constant FactorJournal of the ACM10.1145/3639453Online publication date: 2-Jan-2024
https://doi.org/10.1145/3639453
Ostovari MZarei A(2024)A Better LP Rounding for Feedback Arc Set on TournamentsTheoretical Computer Science10.1016/j.tcs.2024.114768(114768)Online publication date: Aug-2024
https://doi.org/10.1016/j.tcs.2024.114768
Chakrabarty SMakarychev KOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Single-pass pivot algorithm for correlation clustering. keep it simple!Proceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3666402(6412-6421)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3666402
Davies SMoseley BNewman HKrause ABrunskill ECho KEngelhardt BSabato SScarlett J(2023)Fast combinatorial algorithms for min max correlation clusteringProceedings of the 40th International Conference on Machine Learning10.5555/3618408.3618693(7205-7230)Online publication date: 23-Jul-2023
https://dl.acm.org/doi/10.5555/3618408.3618693
Bengali VVeldt NFrommholz IHopfgartner FLee MOakes MLalmas MZhang MSantos R(2023)Faster Approximation Algorithms for Parameterized Graph Clustering and Edge LabelingProceedings of the 32nd ACM International Conference on Information and Knowledge Management10.1145/3583780.3614878(78-87)Online publication date: 21-Oct-2023
https://dl.acm.org/doi/10.1145/3583780.3614878
Cohen-Addad VLee ELi SNewman A(2023)Handling Correlated Rounding Error via Preclustering: A 1.73-approximation for Correlation Clustering2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00065(1082-1104)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00065
Andres BDi Gregorio SIrmai JLange J(2023)A polyhedral study of lifted multicutsDiscrete Optimization10.1016/j.disopt.2022.10075747:COnline publication date: 1-Feb-2023
https://dl.acm.org/doi/10.1016/j.disopt.2022.100757
Ji SLi GZhang DZhang X(2023)Approximation algorithms for the capacitated correlation clustering problem with penaltiesJournal of Combinatorial Optimization10.1007/s10878-022-00930-645:1Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.1007/s10878-022-00930-6
Gullo FMandaglio DTagarelli A(2023)A combinatorial multi-armed bandit approach to correlation clusteringData Mining and Knowledge Discovery10.1007/s10618-023-00937-537:4(1630-1691)Online publication date: 29-Jun-2023
https://doi.org/10.1007/s10618-023-00937-5
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents