{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,25]],"date-time":"2026-03-25T05:50:06Z","timestamp":1774417806183,"version":"3.50.1"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2019,9,23]],"date-time":"2019-09-23T00:00:00Z","timestamp":1569196800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2019,9,23]],"date-time":"2019-09-23T00:00:00Z","timestamp":1569196800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100005934","name":"Malm\u00f6 University","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100005934","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,4]]},"abstract":"<jats:title>Abstract<\/jats:title>\n<jats:p>Clique clustering is the problem of partitioning the vertices of a graph into disjoint clusters, where each cluster forms a clique in the graph, while optimizing some objective function. In online clustering, the input graph is given one vertex at a time, and any vertices that have previously been clustered together are not allowed to be separated. The goal is to maintain a clustering with an objective value close to the optimal solution. For the variant where we want to maximize the number of edges in the clusters, we propose an online algorithm based on the doubling technique.  It has an asymptotic competitive ratio at most 15.646 and a strict competitive ratio at most 22.641. We also show that no deterministic algorithm can have an asymptotic competitive ratio better than\u00a06. For the variant where we want to minimize the number of edges between clusters, we show that the deterministic competitive ratio of the problem is <jats:inline-formula><jats:alternatives><jats:tex-math>$$n-\\omega (1)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>n<\/mml:mi><mml:mo>-<\/mml:mo><mml:mi>\u03c9<\/mml:mi><mml:mo>(<\/mml:mo><mml:mn>1<\/mml:mn><mml:mo>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>, where <jats:italic>n<\/jats:italic> is the number of vertices in the graph.\n<\/jats:p>","DOI":"10.1007\/s00453-019-00625-1","type":"journal-article","created":{"date-parts":[[2019,9,23]],"date-time":"2019-09-23T14:02:38Z","timestamp":1569247358000},"page":"938-965","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Online Clique Clustering"],"prefix":"10.1007","volume":"82","author":[{"given":"Marek","family":"Chrobak","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christoph","family":"D\u00fcrr","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aleksander","family":"Fabijan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1342-8618","authenticated-orcid":false,"given":"Bengt J.","family":"Nilsson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,9,23]]},"reference":[{"issue":"1\u20133","key":"625_CR1","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1023\/B:MACH.0000033116.57574.95","volume":"56","author":"N Bansal","year":"2004","unstructured":"Bansal, N., Blum, A., Chawla, S.: Correlation clustering. Mach. Learn. 56(1\u20133), 89\u2013113 (2004)","journal-title":"Mach. Learn."},{"issue":"3\/4","key":"625_CR2","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1089\/106652799318274","volume":"6","author":"A Ben-Dor","year":"1999","unstructured":"Ben-Dor, A., Shamir, R., Yakhini, Z.: Clustering gene expression patterns. J. Comput. Biol. 6(3\/4), 281\u2013297 (1999)","journal-title":"J. Comput. Biol."},{"key":"625_CR3","volume-title":"Online Computation and Competitive Analysis","author":"A Borodin","year":"1998","unstructured":"Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press, Cambridge (1998)"},{"issue":"6","key":"625_CR4","doi-asserted-by":"publisher","first-page":"1417","DOI":"10.1137\/S0097539702418498","volume":"33","author":"M Charikar","year":"2004","unstructured":"Charikar, M., Chekuri, C., Feder, T., Motwani, R.: Incremental clustering and dynamic information retrieval. SIAM J. Comput. 33(6), 1417\u20131440 (2004)","journal-title":"SIAM J. Comput."},{"key":"625_CR5","unstructured":"Charikar, M., Guruswami, V., Wirth, A.: Clustering with qualitative information. In: Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on, pp. 524\u2013533. IEEE (2003)"},{"key":"625_CR6","unstructured":"Chaudhuri, K., Godfrey, B., Rao, S., Talwar, K.: Paths, trees, and minimum latency tours. In: 44th Symposium on Foundations of Computer Science (FOCS 2003), 11\u201314 October 2003, Cambridge, MA, USA, Proceedings, pp .36\u201345 (2003)"},{"key":"625_CR7","first-page":"101","volume-title":"Lecture Notes in Computer Science","author":"Marek Chrobak","year":"2015","unstructured":"Chrobak, M., D\u00fcrr, C., Nilsson, B.J.: Competitive strategies for online clique clustering. In: Proceedings of the 9th International Conference on Algorithms and Complexity (CIAC\u201915), pp. 101\u2013113 (2015)"},{"issue":"7","key":"625_CR8","doi-asserted-by":"publisher","first-page":"594","DOI":"10.1016\/j.tcs.2009.07.006","volume":"412","author":"M Chrobak","year":"2011","unstructured":"Chrobak, M., Hurand, M.: Better bounds for incremental medians. Theor. Comput. Sci. 412(7), 594\u2013601 (2011)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"625_CR9","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1007\/s00453-007-9005-x","volume":"50","author":"M Chrobak","year":"2008","unstructured":"Chrobak, M., Kenyon, C., Noga, J., Young, N.E.: Incremental medians via online bidding. Algorithmica 50(4), 455\u2013478 (2008)","journal-title":"Algorithmica"},{"issue":"4","key":"625_CR10","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1145\/1189056.1189078","volume":"37","author":"M Chrobak","year":"2006","unstructured":"Chrobak, M., Kenyon-Mathieu, C.: SIGACT news online algorithms column 10: competitiveness via doubling. SIGACT News 37(4), 115\u2013126 (2006)","journal-title":"SIGACT News"},{"key":"625_CR11","first-page":"1","volume-title":"Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques","author":"Erik D. Demaine","year":"2003","unstructured":"Demaine, E.D., Immorlica, N.: Correlation clustering with partial information. In: Proceedings of the 6th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX\u201903), pp. 1\u201313 (2003)"},{"key":"625_CR12","unstructured":"Dessmark, A., Jansson, J., Lingas, A., Lundell, E.-M., Persson, M.: On the approximability of maximum and minimum edge clique partition problems. In: Proceedings of the 12th Computing: The Australasian Theory Symposium (CATS\u201906), pp. 101\u2013105 (2006)"},{"key":"625_CR13","first-page":"221","volume-title":"Lecture Notes in Computer Science","author":"Aleksander Fabijan","year":"2013","unstructured":"Fabijan, A., Nilsson, B.J., Persson, M.: Competitive online clique clustering. In: Proceedings of the 8th International Conference on Algorithms and Complexity (CIAC\u201913), pp. 221\u2013233 (2013)"},{"issue":"5","key":"625_CR14","doi-asserted-by":"publisher","first-page":"887","DOI":"10.1089\/cmb.2004.11.887","volume":"11","author":"A Figueroa","year":"2004","unstructured":"Figueroa, A., Borneman, J., Jiang, T.: Clustering binary fingerprint vectors with missing values for DNA array data analysis. J. Comput. Biol. 11(5), 887\u2013901 (2004)","journal-title":"J. Comput. Biol."},{"issue":"1","key":"625_CR15","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1016\/j.jda.2007.01.004","volume":"6","author":"A Figueroa","year":"2008","unstructured":"Figueroa, A., Goldstein, A., Jiang, T., Kurowski, M., Lingas, A., Persson, M.: Approximate clustering of incomplete fingerprints. J. Discrete Algorithms 6(1), 103\u2013108 (2008)","journal-title":"J. Discrete Algorithms"},{"issue":"8","key":"625_CR16","doi-asserted-by":"publisher","first-page":"3633","DOI":"10.1137\/070698257","volume":"39","author":"G Lin","year":"2010","unstructured":"Lin, G., Nagarajan, C., Rajaraman, R., Williamson, D.P.: A general approach for incremental approximation and hierarchical clustering. SIAM J. Comput. 39(8), 3633\u20133669 (2010)","journal-title":"SIAM J. Comput."},{"key":"625_CR17","doi-asserted-by":"crossref","unstructured":"Mathieu, C., Sankur, O., Schudy, W.: Online correlation clustering. In: 27th International Symposium on Theoretical Aspects of Computer Science (STACS\u201910), pp. 573\u2013584 (2010)","DOI":"10.1137\/1.9781611973075.58"},{"issue":"1\u20132","key":"625_CR18","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1016\/j.dam.2004.01.007","volume":"144","author":"R Shamir","year":"2004","unstructured":"Shamir, R., Sharan, R., Tsur, D.: Cluster graph modification problems. Discrete Appl. Math. 144(1\u20132), 173\u2013182 (2004)","journal-title":"Discrete Appl. Math."},{"key":"625_CR19","doi-asserted-by":"publisher","first-page":"5999","DOI":"10.1128\/AEM.68.12.5999-6004.2002","volume":"68","author":"L Valinsky","year":"2002","unstructured":"Valinsky, L., Vedova, G.D., Jiang, T., Borneman, J.: Oligonucleotide fingerprinting of rRNA genes for analysis of fungal community composition. Appl. Environ. Microbiol. 68, 5999\u20136004 (2002)","journal-title":"Appl. Environ. Microbiol."},{"key":"625_CR20","first-page":"243","volume":"68","author":"L Valinsky","year":"2002","unstructured":"Valinsky, L., Vedova, G.D., Scupham, R.J., Alvey, S., Figueroa, A., Bei Yin, R., Hartin, J., Chrobak, M., Crowley, D.E., Jiang, T., Borneman, J.: Analysis of bacterial community composition by oligonucleotide fingerprinting of rRNA genes. Appl. Environ. Microbiol. 68, 243\u20133250 (2002)","journal-title":"Appl. Environ. Microbiol."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00625-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-019-00625-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00625-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,9,21]],"date-time":"2020-09-21T23:07:01Z","timestamp":1600729621000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-019-00625-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,9,23]]},"references-count":20,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,4]]}},"alternative-id":["625"],"URL":"https:\/\/doi.org\/10.1007\/s00453-019-00625-1","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,9,23]]},"assertion":[{"value":"12 October 2016","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 August 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 September 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}