{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,3]],"date-time":"2026-03-03T23:34:54Z","timestamp":1772580894314,"version":"3.50.1"},"publisher-location":"Cham","reference-count":24,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030394783","type":"print"},{"value":"9783030394790","type":"electronic"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","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":[[2020]]},"DOI":"10.1007\/978-3-030-39479-0_13","type":"book-chapter","created":{"date-parts":[[2020,1,24]],"date-time":"2020-01-24T20:03:47Z","timestamp":1579896227000},"page":"188-201","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Fault Tolerant Clustering with Outliers"],"prefix":"10.1007","author":[{"given":"Tanmay","family":"Inamdar","sequence":"first","affiliation":[]},{"given":"Kasturi","family":"Varadarajan","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,1,25]]},"reference":[{"key":"13_CR1","unstructured":"Ahmadian, S., Swamy, C.: Approximation algorithms for clustering problems with lower bounds and outliers. In: 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, Rome, Italy, 11\u201315 July 2016, pp. 69:1\u201369:15 (2016)"},{"key":"13_CR2","doi-asserted-by":"crossref","unstructured":"Bandyapadhyay, S., Varadarajan, K.R.: Approximate clustering via metric partitioning. In: 27th International Symposium on Algorithms and Computation, ISAAC 2016, Sydney, Australia, 12\u201314 December 2016, pp. 15:1\u201315:13 (2016)","DOI":"10.1145\/2830567"},{"key":"13_CR3","doi-asserted-by":"crossref","unstructured":"Bhaskara, A., Charikar, M., Chlamtac, E., Feige, U., Vijayaraghavan, A.: Detecting high log-densities: an O(n$${}^{\\text{1\/4}}$$) approximation for densest k-subgraph. In: Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, 5\u20138 June 2010, Cambridge, Massachusetts, USA, pp. 201\u2013210 (2010)","DOI":"10.1145\/1806689.1806719"},{"key":"13_CR4","unstructured":"Bhowmick, S., Inamdar, T., Varadarajan, K.R.: Improved approximation for metric multi-cover. CoRR, abs\/1602.04152 (2016)"},{"key":"13_CR5","doi-asserted-by":"crossref","unstructured":"Byrka, J., Pensyl, T., Rybicki, B., Srinivasan, A., Trinh, K.: An improved approximation for k-median and positive correlation in budgeted optimization, vol. 13, pp. 23:1\u201323:31 (2017)","DOI":"10.1145\/2981561"},{"key":"13_CR6","unstructured":"Chakrabarty, D., Goyal, P., Krishnaswamy, R.: The non-uniform k-center problem. In: 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, Rome, Italy, 11\u201315 July 2016, pp. 67:1\u201367:15 (2016)"},{"issue":"2","key":"13_CR7","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1016\/j.jcss.2003.07.014","volume":"68","author":"M Charikar","year":"2004","unstructured":"Charikar, M., Panigrahy, R.: Clustering to minimize the sum of cluster diameters. J. Comput. Syst. Sci. 68(2), 417\u2013441 (2004)","journal-title":"J. Comput. Syst. Sci."},{"key":"13_CR8","unstructured":"Charikar, M., Khuller, S., Mount, D.M., Narasimhan, G.: Algorithms for facility location problems with outliers. In: Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, Washington, DC, USA, 7\u20139 January 2001, pp. 642\u2013651 (2001)"},{"issue":"3","key":"13_CR9","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/S0020-0190(97)00224-X","volume":"65","author":"S Chaudhuri","year":"1998","unstructured":"Chaudhuri, S., Garg, N., Ravi, R.: The p-neighbor k-center problem. Inf. Process. Lett. 65(3), 131\u2013134 (1998)","journal-title":"Inf. Process. Lett."},{"key":"13_CR10","unstructured":"Chen, K.: A constant factor approximation algorithm for k-median clustering with outliers. In: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, San Francisco, California, USA, 20\u201322 January 2008, pp. 826\u2013835 (2008)"},{"issue":"3","key":"13_CR11","doi-asserted-by":"publisher","first-page":"484","DOI":"10.1007\/s00453-009-9282-7","volume":"57","author":"M Gibson","year":"2010","unstructured":"Gibson, M., Kanade, G., Krohn, E., Pirwani, I.A., Varadarajan, K.R.: On metric clustering to minimize the sum of radii. Algorithmica 57(3), 484\u2013498 (2010)","journal-title":"Algorithmica"},{"key":"13_CR12","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/0304-3975(85)90224-5","volume":"38","author":"TF Gonzalez","year":"1985","unstructured":"Gonzalez, T.F.: Clustering to minimize the maximum intercluster distance. Theor. Comput. Sci. 38, 293\u2013306 (1985)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"13_CR13","doi-asserted-by":"publisher","first-page":"36:1","DOI":"10.1145\/2854153","volume":"12","author":"MT Hajiaghayi","year":"2016","unstructured":"Hajiaghayi, M.T., Hu, W., Li, J., Li, S., Saha, B.: A constant factor approximation algorithm for fault-tolerant k-median. ACM Trans. Algorithms 12(3), 36:1\u201336:19 (2016)","journal-title":"ACM Trans. Algorithms"},{"key":"13_CR14","first-page":"36:1","volume":"15","author":"DG Harris","year":"2019","unstructured":"Harris, D.G., Pensyl, T., Srinivasan, A., Trinh, K.: A lottery model for center-type problems with outliers. ACM Trans. Algorithms (TALG) 15, 36:1\u201336:25 (2019)","journal-title":"ACM Trans. Algorithms (TALG)"},{"issue":"3","key":"13_CR15","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/0166-218X(79)90044-1","volume":"1","author":"W-L Hsu","year":"1979","unstructured":"Hsu, W.-L., Nemhauser, G.L.: Easy and hard bottleneck location problems. Discrete Appl. Math. 1(3), 209\u2013215 (1979)","journal-title":"Discrete Appl. Math."},{"issue":"6","key":"13_CR16","doi-asserted-by":"publisher","first-page":"795","DOI":"10.1145\/950620.950621","volume":"50","author":"K Jain","year":"2003","unstructured":"Jain, K., Mahdian, M., Markakis, E., Saberi, A., Vazirani, V.V.: Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP. J. ACM 50(6), 795\u2013824 (2003)","journal-title":"J. ACM"},{"issue":"1\u20132","key":"13_CR17","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/S0304-3975(98)00222-9","volume":"242","author":"S Khuller","year":"2000","unstructured":"Khuller, S., Pless, R., Sussmann, Y.J.: Fault tolerant k-center problems. Theor. Comput. Sci. 242(1\u20132), 237\u2013245 (2000)","journal-title":"Theor. Comput. Sci."},{"key":"13_CR18","doi-asserted-by":"crossref","unstructured":"Krishnaswamy, R., Li, S., Sandeep, S.: Constant approximation for k-median and k-means with outliers via iterative rounding. In: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, 25\u201329 June 2018, pp. 646\u2013659 (2018)","DOI":"10.1145\/3188745.3188882"},{"issue":"2","key":"13_CR19","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/0020-0190(95)00141-X","volume":"56","author":"SO Krumke","year":"1995","unstructured":"Krumke, S.O.: On a generalization of the p-center problem. Inf. Process. Lett. 56(2), 67\u201371 (1995)","journal-title":"Inf. Process. Lett."},{"key":"13_CR20","unstructured":"Kumar, N., Raichel, B.: Fault tolerant clustering revisited. In: Proceedings of the 25th Canadian Conference on Computational Geometry, CCCG 2013, Waterloo, Ontario, Canada, 8\u201310 August 2013 (2013)"},{"key":"13_CR21","doi-asserted-by":"crossref","unstructured":"Manurangsi, P.: Almost-polynomial ratio eth-hardness of approximating densest k-subgraph. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, 19\u201323 June 2017, pp. 954\u2013961 (2017)","DOI":"10.1145\/3055399.3055412"},{"issue":"1","key":"13_CR22","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1007\/s10878-016-0066-0","volume":"34","author":"Y Ran","year":"2017","unstructured":"Ran, Y., Shi, Y., Zhang, Z.: Local ratio method on partial set multi-cover. J. Comb. Optim. 34(1), 302\u2013313 (2017)","journal-title":"J. Comb. Optim."},{"key":"13_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"372","DOI":"10.1007\/978-3-030-04651-4_25","volume-title":"Combinatorial Optimization and Applications","author":"Y Ran","year":"2018","unstructured":"Ran, Y., Shi, Y., Zhang, Z.: Primal dual algorithm for partial set multi-cover. In: Kim, D., Uma, R.N., Zelikovsky, A. (eds.) COCOA 2018. LNCS, vol. 11346, pp. 372\u2013385. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-030-04651-4_25"},{"issue":"4","key":"13_CR24","doi-asserted-by":"publisher","first-page":"51:1","DOI":"10.1145\/1383369.1383382","volume":"4","author":"C Swamy","year":"2008","unstructured":"Swamy, C., Shmoys, D.B.: Fault-tolerant facility location. ACM Trans. Algorithms 4(4), 51:1\u201351:27 (2008)","journal-title":"ACM Trans. Algorithms"}],"container-title":["Lecture Notes in Computer Science","Approximation and Online Algorithms"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-39479-0_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,23]],"date-time":"2021-02-23T22:15:30Z","timestamp":1614118530000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-39479-0_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030394783","9783030394790"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-39479-0_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"25 January 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WAOA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Approximation and Online Algorithms","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Munich","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Germany","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12 September 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13 September 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"waoa2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/algo2019.ak.in.tum.de\/index.php\/menue-waoa\/waoa-overview","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}