{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,24]],"date-time":"2025-06-24T07:09:43Z","timestamp":1750748983328,"version":"3.40.3"},"publisher-location":"Cham","reference-count":20,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030914332"},{"type":"electronic","value":"9783030914349"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021]]},"DOI":"10.1007\/978-3-030-91434-9_4","type":"book-chapter","created":{"date-parts":[[2021,12,3]],"date-time":"2021-12-03T07:04:42Z","timestamp":1638515082000},"page":"39-49","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Approximation Algorithms for the Lower Bounded Correlation Clustering Problem"],"prefix":"10.1007","author":[{"given":"Sai","family":"Ji","sequence":"first","affiliation":[]},{"given":"Yinhong","family":"Dong","sequence":"additional","affiliation":[]},{"given":"Donglei","family":"Du","sequence":"additional","affiliation":[]},{"given":"Dachuan","family":"Xu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,12,4]]},"reference":[{"issue":"5","key":"4_CR1","doi-asserted-by":"publisher","first-page":"1110","DOI":"10.1137\/110848712","volume":"41","author":"N Ailon","year":"2012","unstructured":"Ailon, N., Avigdor-Elgrabli, N., Liberty, E., Zuylen, A.V.: Improved approximation algorithms for bipartite correlation clustering. SIAM J. Comput. 41(5), 1110\u20131121 (2012)","journal-title":"SIAM J. Comput."},{"key":"4_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/978-3-030-17953-3_2","volume-title":"Integer Programming and Combinatorial Optimization","author":"S Ahmadi","year":"2019","unstructured":"Ahmadi, S., Khuller, S., Saha, B.: Min-max correlation clustering via MultiCut. In: Lodi, A., Nagarajan, V. (eds.) IPCO 2019. LNCS, vol. 11480, pp. 13\u201326. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-17953-3_2"},{"key":"4_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1007\/978-3-642-38016-7_21","volume-title":"Approximation and Online Algorithms","author":"S Ahmadian","year":"2013","unstructured":"Ahmadian, S., Swamy, C.: Improved approximation guarantees for lower-bounded facility location. In: Erlebach, T., Persiano, G. (eds.) WAOA 2012. LNCS, vol. 7846, pp. 257\u2013271. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-38016-7_21"},{"issue":"1\u20133","key":"4_CR4","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":"4","key":"4_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2728170","volume":"9","author":"F Bonchi","year":"2015","unstructured":"Bonchi, F., Gionis, A., Gullo, F., Tsourakakis, C.E., Ukkonen, A.: Chromatic correlation clustering. ACM Trans. Knowl. Discov. Data 9(4), 1\u201324 (2015)","journal-title":"ACM Trans. Knowl. Discov. Data"},{"issue":"1","key":"4_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10115-012-0522-9","volume":"35","author":"F Bonchi","year":"2013","unstructured":"Bonchi, F., Gionis, A., Ukkonen, A.: Overlapping correlation clustering. Knowl. Inf. Syst. 35(1), 1\u201332 (2013)","journal-title":"Knowl. Inf. Syst."},{"issue":"3","key":"4_CR7","doi-asserted-by":"publisher","first-page":"360","DOI":"10.1016\/j.jcss.2004.10.012","volume":"71","author":"M Charikar","year":"2005","unstructured":"Charikar, M., Guruswami, V., Wirth, A.: Clustering with qualitative information. J. Comput. Syst. Sci. 71(3), 360\u2013383 (2005)","journal-title":"J. Comput. Syst. Sci."},{"key":"4_CR8","doi-asserted-by":"crossref","unstructured":"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\u2013228 (2015)","DOI":"10.1145\/2746539.2746604"},{"issue":"4","key":"4_CR9","doi-asserted-by":"publisher","first-page":"1312","DOI":"10.1007\/s10878-018-0354-y","volume":"37","author":"T Fukunaga","year":"2018","unstructured":"Fukunaga, T.: LP-based pivoting algorithm for higher-order correlation clustering. J. Comb. Optim. 37(4), 1312\u20131326 (2018). https:\/\/doi.org\/10.1007\/s10878-018-0354-y","journal-title":"J. Comb. Optim."},{"key":"4_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"627","DOI":"10.1007\/978-3-030-58150-3_51","volume-title":"Computing and Combinatorics","author":"L Han","year":"2020","unstructured":"Han, L., Hao, C., Wu, C., Zhang, Z.: Approximation algorithms for the lower-bounded k-median and its generalizations. In: Kim, D., Uma, R.N., Cai, Z., Lee, D.H. (eds.) COCOON 2020. LNCS, vol. 12273, pp. 627\u2013639. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-58150-3_51"},{"key":"4_CR11","unstructured":"Jafarov, J., Kalhan, S., Makarychev, K., Makarychev, Y.: Correlation clustering with asymmetric classification errors. In: Proceedings of the 37th International Conference on Machine Learning, pp. 4641\u20134650 (2020)"},{"key":"4_CR12","doi-asserted-by":"crossref","unstructured":"Li, S.: On facility location with general lower bounds. In: Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2279\u20132290 (2019)","DOI":"10.1137\/1.9781611975482.138"},{"issue":"5","key":"4_CR13","doi-asserted-by":"publisher","first-page":"3065","DOI":"10.1109\/TIT.2019.2940246","volume":"66","author":"P Li","year":"2019","unstructured":"Li, P., Puleo, G.J., Milenkovic, O.: Motif and hypergraph correlation clustering. IEEE Trans. Inf. Theory 66(5), 3065\u20133078 (2019)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"4_CR14","unstructured":"Makarychev, K., Makarychev, Y., Vijayaraghavan, A.: Correlation clustering with noisy partial information. In: Proceedings of the 28th Annual Conference Computational Learning Theory, pp. 1321\u20131342 (2015)"},{"key":"4_CR15","doi-asserted-by":"crossref","unstructured":"Mathieu, C., Schudy, W.: Correlation clustering with noisy input. In: Proceedings of the 21th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 712\u2013728 (2010)","DOI":"10.1137\/1.9781611973075.58"},{"issue":"3","key":"4_CR16","doi-asserted-by":"publisher","first-page":"1857","DOI":"10.1137\/140994198","volume":"25","author":"GJ Puleo","year":"2015","unstructured":"Puleo, G.J., Milenkovic, O.: Correlation clustering with constrained cluster sizes and extended weights bounds. SIAM J. Optim. 25(3), 1857\u20131872 (2015)","journal-title":"SIAM J. Optim."},{"issue":"4","key":"4_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1824777.1824789","volume":"6","author":"Z Svitkina","year":"2010","unstructured":"Svitkina, Z.: Lower-bounded facility location. ACM Trans. Algorithms 6(4), 1\u201316 (2010)","journal-title":"ACM Trans. Algorithms"},{"key":"4_CR18","unstructured":"Swamy, C.: Correlation clustering: maximizing agreements via semidefinite programming. In: Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 526\u2013527 (2004)"},{"key":"4_CR19","unstructured":"Saha, B., Subramanian, S.: Correlation clustering with same-cluster queries bounded by optimal cost. In: Proceedings of the 27th Annual European Symposium on Algorithms, pp. 81:1\u201381:17 (2019)"},{"key":"4_CR20","doi-asserted-by":"crossref","unstructured":"Veldt, N., Gleich, D.F., Wirth, A.: A correlation clustering framework for community detection. In: Proceedings of the 27th World Wide Web Conference, pp. 439\u2013448 (2018)","DOI":"10.1145\/3178876.3186110"}],"container-title":["Lecture Notes in Computer Science","Computational Data and Social Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-91434-9_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T08:40:16Z","timestamp":1710232816000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-91434-9_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030914332","9783030914349"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-91434-9_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"4 December 2021","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CSoNet","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Computational Data and Social Networks","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15 November 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 November 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"csonet2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/csonet-conf.github.io\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"57","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"24","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"8","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"42% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"6","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}