{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T01:41:11Z","timestamp":1742953271874,"version":"3.40.3"},"publisher-location":"Cham","reference-count":35,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031598340"},{"type":"electronic","value":"9783031598357"}],"license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024]]},"DOI":"10.1007\/978-3-031-59835-7_2","type":"book-chapter","created":{"date-parts":[[2024,5,21]],"date-time":"2024-05-21T07:05:03Z","timestamp":1716275103000},"page":"14-27","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Separating $$k\\text {-}\\textsc {Median}$$ from\u00a0the\u00a0Supplier Version"],"prefix":"10.1007","author":[{"given":"Aditya","family":"Anand","sequence":"first","affiliation":[]},{"given":"Euiwoong","family":"Lee","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,5,22]]},"reference":[{"key":"2_CR1","unstructured":"Adamczyk, M., Byrka, J., Marcinkowski, J., Meesum, S.M., Wlodarczyk, M.: Constant-factor FPT approximation for capacitated k-median. In: 27th Annual European Symposium on Algorithms (ESA 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2019)"},{"key":"2_CR2","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1613\/jair.1.14883","volume":"78","author":"A Agrawal","year":"2023","unstructured":"Agrawal, A., Inamdar, T., Saurabh, S., Xue, J.: Clustering what matters: optimal approximation for clustering with outliers. J. Artif. Intell. Res. 78, 143\u2013166 (2023)","journal-title":"J. Artif. Intell. Res."},{"key":"2_CR3","doi-asserted-by":"crossref","unstructured":"Arya, V., Garg, N., Khandekar, R., Meyerson, A., Munagala, K., Pandit, V.: Local search heuristic for k-median and facility location problems. In: Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, pp. 21\u201329 (2001)","DOI":"10.1145\/380752.380755"},{"key":"2_CR4","doi-asserted-by":"crossref","unstructured":"Badanidiyuru, A., Kleinberg, R., Lee, H.: Approximating low-dimensional coverage problems. In: Proceedings of the Twenty-Eighth Annual Symposium on Computational Geometry, pp. 161\u2013170 (2012)","DOI":"10.1145\/2261250.2261274"},{"key":"2_CR5","unstructured":"Bandyapadhyay, S., Fomin, F.V., Golovach, P.A., Purohit, N., Simonov, K.: FPT approximation for fair minimum-load clustering. In: 17th International Symposium on Parameterized and Exact Computation (2022)"},{"key":"2_CR6","unstructured":"Bandyapadhyay, S., Lochet, W., Saurabh, S.: FPT constant-approximations for capacitated clustering to minimize the sum of cluster radii. In: 39th International Symposium on Computational Geometry (SoCG 2023). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik (2023)"},{"key":"2_CR7","doi-asserted-by":"crossref","unstructured":"Bartal, Y.: On approximating arbitrary metrices by tree metrics. In: Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, pp. 161\u2013168 (1998)","DOI":"10.1145\/276698.276725"},{"issue":"2","key":"2_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2981561","volume":"13","author":"J Byrka","year":"2017","unstructured":"Byrka, J., Pensyl, T., Rybicki, B., Srinivasan, A., Trinh, K.: An improved approximation for k-median and positive correlation in budgeted optimization. ACM Trans. Algorithms (TALG) 13(2), 1\u201331 (2017)","journal-title":"ACM Trans. Algorithms (TALG)"},{"key":"2_CR9","doi-asserted-by":"crossref","unstructured":"Charikar, M., Chekuri, C., Goel, A., Guha, S.: Rounding via trees: deterministic approximation algorithms for group Steiner trees and k-median. In: Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, pp. 114\u2013123 (1998)","DOI":"10.1145\/276698.276719"},{"key":"2_CR10","doi-asserted-by":"crossref","unstructured":"Charikar, M., Guha, S.: Improved combinatorial algorithms for the facility location and k-median problems. In: 40th Annual Symposium on Foundations of Computer Science (Cat. No. 99CB37039), pp. 378\u2013388. IEEE (1999)","DOI":"10.1109\/SFFCS.1999.814609"},{"key":"2_CR11","doi-asserted-by":"crossref","unstructured":"Charikar, M., Guha, S., Tardos, \u00c9., Shmoys, D.B.: A constant-factor approximation algorithm for the k-median problem. In: Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, pp. 1\u201310 (1999)","DOI":"10.1145\/301250.301257"},{"key":"2_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1007\/978-3-642-31594-7_17","volume-title":"Automata, Languages, and Programming","author":"M Charikar","year":"2012","unstructured":"Charikar, M., Li, S.: A dependent LP-rounding approach for the k-median problem. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012. LNCS, vol. 7391, pp. 194\u2013205. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-31594-7_17"},{"key":"2_CR13","doi-asserted-by":"crossref","unstructured":"Charikar, M., Makarychev, K., Makarychev, Y.: Integrality gaps for Sherali-Adams relaxations. In: Proceedings of the Forty-First Annual ACM symposium on Theory of Computing, pp. 283\u2013292 (2009)","DOI":"10.1145\/1536414.1536455"},{"key":"2_CR14","unstructured":"Cohen-Addad, V., Gupta, A., Kumar, A., Lee, E., Li, J.: Tight FPT approximations for k-median and k-means. In: 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), vol.\u00a0132, pp. 42\u20131. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik (2019)"},{"key":"2_CR15","unstructured":"Cohen-Addad, V., Li, J.: On the fixed-parameter tractability of capacitated clustering. In: 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), vol.\u00a0132, p. 41-1. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik (2019)"},{"key":"2_CR16","doi-asserted-by":"crossref","unstructured":"Cohen-Addad\u00a0Viallat, V., Grandoni, F., Lee, E., Schwiegelshohn, C.: Breaching the 2 LMP approximation barrier for facility location with applications to k-median. In: Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 940\u2013986. SIAM (2023)","DOI":"10.1137\/1.9781611977554.ch37"},{"issue":"4","key":"2_CR17","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U Feige","year":"1998","unstructured":"Feige, U.: A threshold of ln n for approximating set cover. J. ACM (JACM) 45(4), 634\u2013652 (1998)","journal-title":"J. ACM (JACM)"},{"key":"2_CR18","doi-asserted-by":"crossref","unstructured":"Feldman, D., Langberg, M.: A unified framework for approximating and clustering data. In: Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing, pp. 569\u2013578 (2011)","DOI":"10.1145\/1993636.1993712"},{"key":"2_CR19","unstructured":"Feng, Q., Zhang, Z., Huang, Z., Xu, J., Wang, J.: A unified framework of FPT approximation algorithms for clustering problems. In: 31st International Symposium on Algorithms and Computation (ISAAC 2020). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik (2020)"},{"key":"2_CR20","doi-asserted-by":"crossref","unstructured":"Gowda, K.N., Pensyl, T., Srinivasan, A., Trinh, K.: Improved bi-point rounding algorithms and a golden barrier for k-median. In: Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 987\u20131011. SIAM (2023)","DOI":"10.1137\/1.9781611977554.ch38"},{"key":"2_CR21","doi-asserted-by":"publisher","first-page":"106383","DOI":"10.1016\/j.ipl.2023.106383","volume":"182","author":"D Goyal","year":"2023","unstructured":"Goyal, D., Jaiswal, R.: Tight FPT approximation for socially fair clustering. Inf. Process. Lett. 182, 106383 (2023)","journal-title":"Inf. Process. Lett."},{"key":"2_CR22","unstructured":"Goyal, D., Jaiswal, R., Kumar, A.: FPT approximation for constrained metric k-median\/means. In: 15th International Symposium on Parameterized and Exact Computation. p.\u00a01 (2020)"},{"issue":"1","key":"2_CR23","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1006\/jagm.1998.0993","volume":"31","author":"S Guha","year":"1999","unstructured":"Guha, S., Khuller, S.: Greedy strikes back: improved facility location algorithms. J. Algorithms 31(1), 228\u2013248 (1999)","journal-title":"J. Algorithms"},{"issue":"4","key":"2_CR24","doi-asserted-by":"publisher","first-page":"798","DOI":"10.1145\/502090.502098","volume":"48","author":"J H\u00e5stad","year":"2001","unstructured":"H\u00e5stad, J.: Some optimal inapproximability results. J. ACM (JACM) 48(4), 798\u2013859 (2001)","journal-title":"J. ACM (JACM)"},{"key":"2_CR25","unstructured":"Inamdar, T., Varadarajan, K.: Capacitated sum-of-radii clustering: an FPT approximation. In: 28th Annual European Symposium on Algorithms (ESA 2020). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik (2020)"},{"issue":"6","key":"2_CR26","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 (JACM) 50(6), 795\u2013824 (2003)","journal-title":"J. ACM (JACM)"},{"issue":"2","key":"2_CR27","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1145\/375827.375845","volume":"48","author":"K Jain","year":"2001","unstructured":"Jain, K., Vazirani, V.V.: Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation. J. ACM (JACM) 48(2), 274\u2013296 (2001)","journal-title":"J. ACM (JACM)"},{"key":"2_CR28","doi-asserted-by":"crossref","unstructured":"Jain, P., et al.: Parameterized approximation scheme for biclique-free max k-weight SAT and max coverage. In: Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 3713\u20133733. SIAM (2023)","DOI":"10.1137\/1.9781611977554.ch143"},{"key":"2_CR29","unstructured":"Jaiswal, R., Kumar, A.: Clustering what matters in constrained settings. In: 34th International Symposium on Algorithms and Computation (2023)"},{"key":"2_CR30","doi-asserted-by":"crossref","unstructured":"Khot, S.: On the power of unique 2-prover 1-round games. In: Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing, pp. 767\u2013775 (2002)","DOI":"10.1145\/509907.510017"},{"key":"2_CR31","doi-asserted-by":"crossref","unstructured":"Li, S., Svensson, O.: Approximating k-median via pseudo-approximation. In: Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, pp. 901\u2013910 (2013)","DOI":"10.1145\/2488608.2488723"},{"issue":"5","key":"2_CR32","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1016\/0020-0190(92)90208-D","volume":"44","author":"JH Lin","year":"1992","unstructured":"Lin, J.H., Vitter, J.S.: Approximation algorithms for geometric median problems. Inf. Process. Lett. 44(5), 245\u2013249 (1992)","journal-title":"Inf. Process. Lett."},{"key":"2_CR33","doi-asserted-by":"crossref","unstructured":"Lin, J.H., Vitter, J.S.: e-approximations with minimum packing constraint violation. In: Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing, pp. 771\u2013782 (1992)","DOI":"10.1145\/129712.129787"},{"key":"2_CR34","unstructured":"Manurangsi, P.: A note on max k-vertex cover: faster FPT-AS, smaller approximate kernel and improved approximation. In: 2nd Symposium on Simplicity in Algorithms (2019)"},{"key":"2_CR35","doi-asserted-by":"publisher","first-page":"709","DOI":"10.1007\/s11081-020-09503-0","volume":"21","author":"Y Xu","year":"2020","unstructured":"Xu, Y., M\u00f6hring, R.H., Xu, D., Zhang, Y., Zou, Y.: A constant FPT approximation algorithm for hard-capacitated k-means. Optim. Eng. 21, 709\u2013722 (2020)","journal-title":"Optim. Eng."}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-59835-7_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,19]],"date-time":"2024-11-19T14:31:53Z","timestamp":1732026713000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-59835-7_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9783031598340","9783031598357"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-59835-7_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"22 May 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"IPCO","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Integer Programming and Combinatorial Optimization","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Wroc\u0142aw","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Poland","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"3 July 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"5 July 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ipco2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/ipco2024.ii.uni.wroc.pl\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}