{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,3]],"date-time":"2025-08-03T22:58:51Z","timestamp":1754261931042,"version":"3.40.3"},"publisher-location":"Cham","reference-count":19,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319774039"},{"type":"electronic","value":"9783319774046"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-77404-6_2","type":"book-chapter","created":{"date-parts":[[2018,3,12]],"date-time":"2018-03-12T10:03:11Z","timestamp":1520848991000},"page":"14-27","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Approximate Correlation Clustering Using Same-Cluster Queries"],"prefix":"10.1007","author":[{"given":"Nir","family":"Ailon","sequence":"first","affiliation":[]},{"given":"Anup","family":"Bhattacharya","sequence":"additional","affiliation":[]},{"given":"Ragesh","family":"Jaiswal","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,3,13]]},"reference":[{"key":"2_CR1","unstructured":"Ailon, N., Bhattacharya, A., Jaiswal, R., Kumar, A.: Approximate clustering with same-cluster queries (2017). CoRR, abs\/1704.01862. To Appear in ITCS 2018"},{"key":"2_CR2","doi-asserted-by":"crossref","unstructured":"Angelidakis, H., Makarychev, K., Makarychev, Y.: Algorithms for stable and perturbation-resilient problems. In: STOC, pp. 438\u2013451 (2017)","DOI":"10.1145\/3055399.3055487"},{"key":"2_CR3","unstructured":"Ashtiani, H., Kushagra, S., Ben-David, S.: Clustering with same-cluster queries. In: NIPS, pp. 3216\u20133224 (2016)"},{"key":"2_CR4","unstructured":"Awasthi, P., Balcan, M.-F, Voevodski, K.: Local algorithms for interactive clustering. In: ICML, pp. 550\u2013558 (2014)"},{"key":"2_CR5","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"316","DOI":"10.1007\/978-3-540-87987-9_27","volume-title":"Algorithmic Learning Theory","author":"M-F Balcan","year":"2008","unstructured":"Balcan, M.-F., Blum, A.: Clustering with interactive feedback. In: Freund, Y., Gy\u00f6rfi, L., Tur\u00e1n, G., Zeugmann, T. (eds.) ALT 2008. LNCS (LNAI), vol. 5254, pp. 316\u2013328. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-87987-9_27"},{"issue":"2","key":"2_CR6","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1145\/2450142.2450144","volume":"60","author":"M-F Balcan","year":"2013","unstructured":"Balcan, M.-F., Blum, A., Gupta, A.: Clustering under approximation stability. J. ACM (JACM) 60(2), 8 (2013)","journal-title":"J. ACM (JACM)"},{"issue":"1","key":"2_CR7","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1137\/140981575","volume":"45","author":"MF Balcan","year":"2016","unstructured":"Balcan, M.F., Liang, Y.: Clustering under perturbation resilience. SIAM J. Comput. 45(1), 102\u2013155 (2016)","journal-title":"SIAM J. Comput."},{"issue":"1\u20133","key":"2_CR8","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","key":"2_CR9","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."},{"issue":"3","key":"2_CR10","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1145\/1236457.1236459","volume":"54","author":"I Dinur","year":"2007","unstructured":"Dinur, I.: The PCP theorem by gap amplification. J. ACM 54(3), 12 (2007)","journal-title":"J. ACM"},{"issue":"7","key":"2_CR11","doi-asserted-by":"publisher","first-page":"1430","DOI":"10.1016\/j.jcss.2014.04.015","volume":"80","author":"FV Fomin","year":"2014","unstructured":"Fomin, F.V., Kratsch, S., Pilipczuk, M., Pilipczuk, M., Villanger, Y.: Tight bounds for parameterized complexity of cluster editing with a small number of clusters. J. Comput. Syst. Sci. 80(7), 1430\u20131447 (2014)","journal-title":"J. Comput. Syst. Sci."},{"key":"2_CR12","doi-asserted-by":"crossref","unstructured":"Giotis, I., Guruswami, V.: Correlation clustering with a fixed number of clusters. In: SODA, pp. 1167\u20131176 (2006)","DOI":"10.1145\/1109557.1109686"},{"issue":"2","key":"2_CR13","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the complexity of k-SAT. J. Comput. Syst. Sci. 62(2), 367\u2013375 (2001)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"2_CR14","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"2_CR15","unstructured":"Makarychev, K., Makarychev, Y., Vijayaraghavan, A.: Correlation clustering with noisy partial information. In: COLT, pp. 1321\u20131342 (2015)"},{"key":"2_CR16","doi-asserted-by":"crossref","unstructured":"Manurangsi, P.: Almost-polynomial ratio ETH-hardness of approximating densest $$k$$-subgraph. CoRR, abs\/1611.05991 (2016)","DOI":"10.1145\/3055399.3055412"},{"key":"2_CR17","doi-asserted-by":"crossref","unstructured":"Mathieu, C., Schudy, W.: Correlation clustering with noisy input. In: ACM-SIAM Symposium on Discrete Algorithms, pp. 712\u2013728 (2010)","DOI":"10.1137\/1.9781611973075.58"},{"key":"2_CR18","unstructured":"Mazumdar, A., Saha, B.: Query complexity of clustering with side information. arXiv preprint arXiv:1706.07719 (2017)"},{"key":"2_CR19","unstructured":"Voevodski, K., Balcan, M.-F., R\u00f6glin, H., Teng, S.-H., Xia, Y.: Efficient clustering with limited distance information. In: Conference on Uncertainty in Artificial Intelligence, pp. 632\u2013640 (2010)"}],"container-title":["Lecture Notes in Computer Science","LATIN 2018: Theoretical Informatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-77404-6_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,7]],"date-time":"2024-03-07T16:00:16Z","timestamp":1709827216000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-77404-6_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319774039","9783319774046"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-77404-6_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"13 March 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"LATIN","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Latin American Symposium on Theoretical Informatics","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Buenos Aires","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Argentina","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16 April 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 April 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"latin2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/latin2018.dc.uba.ar\/#","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}