×

Correlation clustering with constrained cluster sizes and extended weights bounds. (English) Zbl 1337.68296

Summary: We consider the problem of correlation clustering on graphs with constraints on both the cluster sizes and the positive and negative weights of edges. Our contributions are twofold: first, we introduce the problem of correlation clustering with bounded cluster sizes. Second, we extend the regime of weight values for which the clustering may be performed with constant approximation guarantees in polynomial time and apply the results to the bounded cluster size problem.

MSC:

68W25 Approximation algorithms
90C05 Linear programming
90C35 Programming involving graphs or networks

Software:

SING; AS 136
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] N. Ailon, M. Charikar, and A. Newman, {\it Aggregating inconsistent information: Ranking and clustering}, in Proceedings of the 37th Annual ACM Symposium on Theory of Computing, ACM, New York, 2005, pp. 684-693. · Zbl 1192.90252
[2] N. Ailon, M. Charikar, and A. Newman, {\it Aggregating inconsistent information: Ranking and clustering}, J. ACM, 55 (2008), 23. · Zbl 1325.68102
[3] K. Andreev and H. Racke, {\it Balanced graph partitioning}, Theory Comput. Syst., 39 (2006), pp. 929-939. · Zbl 1113.68069
[4] N. Bansal, A. Blum, and S. Chawla, {\it Correlation clustering}, in Proceedings of the 43rd Symposium on Foundations of Computer Science, FOCS ’02, Washington, DC, 2002, IEEE Computer Society, Los Alamitos, CA, pp. 238-247. · Zbl 1089.68085
[5] N. Bansal, A. Blum, and S. Chawla, {\it Correlation clustering}, Mach. Learn., 56 (2004), pp. 89-113. · Zbl 1089.68085
[6] J. Bartholdi, III, C. A. Tovey, and M. A. Trick, {\it Voting schemes for which it can be difficult to tell who won the election}, Social Choice Welfare, 6 (1989), pp. 157-165. · Zbl 0672.90004
[7] J. M. Carlson and J. Doyle, {\it Complexity and robustness}, Proc. Natl. Acad. Sci. USA, 99 (2002), pp. 2538-2545.
[8] P. Charbit, S. Thomassé, and A. Yeo, {\it The minimum feedback arc set problem is NP-hard for tournaments}, Combin. Probab. Comput., 16 (2007), pp. 1-4. · Zbl 1120.05038
[9] M. Charikar, V. Guruswami, and A. Wirth, {\it Clustering with qualitative information}, in Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, FOCS ’03, Washington, DC, 2003, IEEE Computer Society, Los Alamitos, CA, pp. 524-533. · Zbl 1094.68075
[10] M. Charikar, V. Guruswami, and A. Wirth, {\it Clustering with qualitative information}, J. Comput. Syst. Sci., 71 (2005), pp. 360-383. · Zbl 1094.68075
[11] S. Chawla, R. Krauthgamer, R. Kumar, Y. Rabani, and D. Sivakumar, {\it On the hardness of approximating multicut and sparsest-cut}, Comput. Complexity, 15 (2006), pp. 94-114. · Zbl 1132.68418
[12] S. Chawla, K. Makarychev, T. Schramm, and G. Yaroslavtsev, {\it Near Optimal LP Rounding Algorithm for Correlation Clustering on Complete and Complete k-Partite Graphs}, preprint, arXiv:1412.0681, 2014. · Zbl 1321.68495
[13] F. Chierichetti, N. Dalvi, and R. Kumar, {\it Correlation clustering in mapreduce}, in Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, New York, 2014, pp. 641-650.
[14] M.-C. Costa, L. Létocart, and F. Roupin, {\it Minimal multicut and maximal integer multiflow: A survey}, Eur. J. Oper. Res., 162 (2005), pp. 55-69. · Zbl 1132.90306
[15] F. Dehne, M. A. Langston, X. Luo, S. Pitre, P. Shaw, and Y. Zhang, {\it The cluster editing problem: Implementations and experiments}, in Parameterized and Exact Computation, Springer, New York, 2006, pp. 13-24. · Zbl 1154.68451
[16] E. D. Demaine, D. Emanuel, A. Fiat, and N. Immorlica, {\it Correlation clustering in general weighted graphs}, Theoret. Comput. Sci., 361 (2006), pp. 172-187. · Zbl 1099.68074
[17] E. D. Demaine and N. Immorlica, {\it Correlation clustering with partial information}, in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, Springer, Berlin, 2003, pp. 1-13. · Zbl 1202.68479
[18] R. Di Natale, A. Ferro, R. Giugno, M. Mongiov\`\i, A. Pulvirenti, and D. Shasha, {\it Sing: Subgraph search in non-homogeneous graphs}, BMC Bioinform., 11 (2010), 96.
[19] C. Dwork, R. Kumar, M. Naor, and D. Sivakumar, {\it Rank aggregation methods for the web}, in Proceedings of the 10th International Conference on World Wide Web, ACM, New York, 2001, pp. 613-622.
[20] D. Emanuel and A. Fiat, {\it Correlation clustering-minimizing disagreements on arbitrary weighted graphs}, in Algorithms-ESA 2003, Springer, Berlin, 2003, pp. 208-220. · Zbl 1266.68228
[21] F. Farnoud and O. Milenkovic, {\it An axiomatic approach to constructing distances for rank comparison and aggregation}, IEEE Trans. Inform. Theory, 60 (2014), pp. 6417-6439. · Zbl 1360.94129
[22] R. L. Ferreira Cordeiro, C. Traina Junior, A. J. Machado Traina, J. López, U. Kang, and C. Faloutsos, {\it Clustering very large multi-dimensional datasets with MapReduce}, in Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, New York, 2011, pp. 690-698.
[23] H. N. Gabow, {\it An efficient reduction technique for degree-constrained subgraph and bidirected network flow problems}, in Proceedings of the 15th Annual ACM Symposium on Theory of Computing, STOC ’83, New York, ACM, New York, 1983, pp. 448-456.
[24] A. Gionis, H. Mannila, and P. Tsaparas, {\it Clustering aggregation}, ACM Trans. Knowl. Discov. Data (TKDD), 1 (2007), p. 4.
[25] J. A. Hartigan and M. A. Wong, {\it Algorithm as 136: A k-means clustering algorithm}, Appl. Statistics, 28 (1979), pp. 100-108. · Zbl 0447.62062
[26] P. Hell and D. G. Kirkpatrick, {\it Algorithms for degree constrained graph factors of minimum deficiency}, J. Algorithms, 14 (1993), pp. 115-138. · Zbl 0764.68118
[27] N. Karmarkar and K. Ramakrishnan, {\it Computational results of an interior point algorithm for large scale linear programming}, Math. Program., 52 (1991), pp. 555-586. · Zbl 0739.90042
[28] R. Khandekar, K. Hildrum, S. Parekh, D. Rajan, J. Sethuraman, and J. Wolf, {\it Bounded size graph clustering with applications to stream processing}, in LIPIcs-Leibniz International Proceedings in Informatics, Vol. 4, Schloss Dagstuhl-Leibniz-Zentrum für Informatik, Wadern, Germany, 2009. · Zbl 1248.68219
[29] S. Khot, {\it On the power of unique 2-prover 1-round games}, in Proceedings of the 34th Annual ACM Symposium on Theory of Computing, ACM, New York, 2002, pp. 767-775. · Zbl 1192.68367
[30] L. Lovász and M. D. Plummer, {\it Matching Theory}, AMS Chelsea, Providence, RI, 2009.
[31] S. Mehrotra, {\it On the implementation of a primal-dual interior point method}, SIAM J. Optim., 2 (1992), pp. 575-601. · Zbl 0773.90047
[32] O. Milenkovic, G. Alterovitz, G. Battail, T. P. Coleman, J. Hagenauer, S. P. Meyn, N. Price, M. F. Ramoni, I. Shmulevich, and W. Szpankowski, {\it Introduction to the special issue on information theory in molecular biology and neuroscience}, IEEE Trans. Inform. Theory, (2010), pp. 649-652.
[33] M. E. Newman, {\it Finding community structure in networks using the eigenvectors of matrices}, Phys. Rev. E (3), 74 (2006), 036104.
[34] X. Pan, D. Papailiopoulos, S. Oymak, B. Recht, K. Ramchandran, and M. I. Jordan, {\it Parallel Correlation Clustering on Big Graphs}, preprint, arxiv:1507.05086[cs.DC], 2015.
[35] R. Shamir, R. Sharan, and D. Tsur, {\it Cluster graph modification problems}, Discrete Appl. Math., 144 (2004), pp. 173-182. · Zbl 1068.68107
[36] D. Steurer and N. Vishnoi, {\it Connections Between Unique Games and Multicut}, Technical report TR09-125, Electronic Colloquium on Computational Complexity, 2009.
[37] C. Swamy, {\it Correlation clustering: maximizing agreements via semidefinite programming}, in Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2004, pp. 526-527. · Zbl 1318.68197
[38] A. van Zuylen and D. P. Williamson, {\it Deterministic pivoting algorithms for constrained ranking and clustering problems}, Math. Oper. Res., 34 (2009), pp. 594-620. · Zbl 1216.68343
[39] J. Yarkony, A. Ihler, and C. C. Fowlkes, {\it Fast planar correlation clustering for image segmentation}, in Computer Vision-ECCV 2012, Springer, Berlin, 2012, pp. 568-581.
[40] C. Zhang, J. Yarkony, and F. A. Hamprecht, {\it Cell detection and segmentation using correlation clustering}, in Medical Image Computing and Computer-Assisted Intervention-MICCAI 2014, Springer, Cham, Switzerland, 2014, pp. 9-16.
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.