{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T02:32:44Z","timestamp":1743042764560,"version":"3.40.3"},"publisher-location":"Cham","reference-count":31,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030808785"},{"type":"electronic","value":"9783030808792"}],"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-80879-2_8","type":"book-chapter","created":{"date-parts":[[2021,7,5]],"date-time":"2021-07-05T08:10:56Z","timestamp":1625472656000},"page":"113-126","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["To Close Is Easier Than To Open: Dual Parameterization To k-Median"],"prefix":"10.1007","author":[{"given":"Jaros\u0142aw","family":"Byrka","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Szymon","family":"Dudycz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pasin","family":"Manurangsi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jan","family":"Marcinkowski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Micha\u0142","family":"W\u0142odarczyk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,7,6]]},"reference":[{"key":"8_CR1","doi-asserted-by":"publisher","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. Leibniz International Proceedings in Informatics (LIPIcs), vol. 144, pp. 1:1\u20131:14. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2019). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2019.1","DOI":"10.4230\/LIPIcs.ESA.2019.1"},{"issue":"4","key":"8_CR2","doi-asserted-by":"publisher","first-page":"844","DOI":"10.1145\/210332.210337","volume":"42","author":"N Alon","year":"1995","unstructured":"Alon, N., Yuster, R., Zwick, U.: Color-coding. J. ACM 42(4), 844\u2013856 (1995). https:\/\/doi.org\/10.1145\/210332.210337","journal-title":"J. ACM"},{"issue":"3","key":"8_CR3","doi-asserted-by":"publisher","first-page":"544","DOI":"10.1137\/S0097539702416402","volume":"33","author":"V Arya","year":"2004","unstructured":"Arya, V., Garg, N., Khandekar, R., Meyerson, A., Munagala, K., Pandit, V.: Local search heuristics for k-median and facility location problems. SIAM J. Comput. 33(3), 544\u2013562 (2004). https:\/\/doi.org\/10.1137\/S0097539702416402","journal-title":"SIAM J. Comput."},{"key":"8_CR4","doi-asserted-by":"publisher","unstructured":"Bhattacharyya, A., Ghoshal, S., Karthik C. S., Manurangsi, P.: Parameterized intractability of even set and shortest vector problem from gap-ETH. In: 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, Prague, Czech Republic, 9\u201313 July 2018, pp. 17:1\u201317:15 (2018). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2018.17","DOI":"10.4230\/LIPIcs.ICALP.2018.17"},{"key":"8_CR5","doi-asserted-by":"publisher","unstructured":"Byrka, J., Pensyl, T., Rybicki, B., Srinivasan, A., Trinh, K.: An improved approximation for k-median, and positive correlation in budgeted optimization. In: Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 737\u2013756. SIAM (2015). https:\/\/doi.org\/10.1145\/2981561","DOI":"10.1145\/2981561"},{"key":"8_CR6","doi-asserted-by":"publisher","unstructured":"Byrka, J., Rybicki, B., Uniyal, S.: An approximation algorithm for uniform capacitated k-median problem with $$1+\\epsilon $$ capacity violation. In: Proceedings of the 18th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2016, Li\u00e8ge, Belgium, 1\u20133 June 2016, pp. 262\u2013274 (2016). https:\/\/doi.org\/10.1007\/978-3-319-33461-5_22","DOI":"10.1007\/978-3-319-33461-5_22"},{"key":"8_CR7","doi-asserted-by":"publisher","unstructured":"Chalermsook, P., et al.: From gap-ETH to FPT-inapproximability: clique, dominating set, and more. In: 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pp. 743\u2013754 (October 2017). https:\/\/doi.org\/10.1109\/FOCS.2017.74","DOI":"10.1109\/FOCS.2017.74"},{"key":"8_CR8","doi-asserted-by":"publisher","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 30th Annual ACM Symposium on the Theory of Computing, Dallas, Texas, USA, 23\u201326 May 1998, pp. 114\u2013123 (1998). https:\/\/doi.org\/10.1145\/276698.276719","DOI":"10.1145\/276698.276719"},{"key":"8_CR9","doi-asserted-by":"publisher","unstructured":"Charikar, M., Guha, S., Tardos, \u00c9., Shmoys, D.B.: A constant-factor approximation algorithm for the k-median problem. In: Proceedings of the 31st annual ACM Symposium on Theory of Computing, pp. 1\u201310. ACM (1999). https:\/\/doi.org\/10.1145\/301250.301257","DOI":"10.1145\/301250.301257"},{"key":"8_CR10","doi-asserted-by":"publisher","unstructured":"Chitnis, R., Feldmann, A.E., Manurangsi, P.: Parameterized approximation algorithms for bidirected Steiner network problems. In: 26th Annual European Symposium on Algorithms, ESA 2018. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2018). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2018.20","DOI":"10.4230\/LIPIcs.ESA.2018.20"},{"key":"8_CR11","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-019-00580-x","author":"R Chitnis","year":"2019","unstructured":"Chitnis, R., Feldmann, A.E., Such\u00fd, O.: A tight lower bound for planar Steiner orientation. Algorithmica (2019). https:\/\/doi.org\/10.1007\/s00453-019-00580-x","journal-title":"Algorithmica"},{"key":"8_CR12","doi-asserted-by":"publisher","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. Leibniz International Proceedings in Informatics (LIPIcs), vol. 132, pp. 42:1\u201342:14. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2019). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2019.42","DOI":"10.4230\/LIPIcs.ICALP.2019.42"},{"key":"8_CR13","doi-asserted-by":"publisher","unstructured":"Cohen-Addad, V., Li, J.: On the fixed-parameter tractability of capacitated clustering. In: Baier, C., Chatzigiannakis, I., Flocchini, P., Leonardi, S. (eds.) 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019. Leibniz International Proceedings in Informatics (LIPIcs), vol. 132, pp. 41:1\u201341:14. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2019). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2019.41","DOI":"10.4230\/LIPIcs.ICALP.2019.41"},{"key":"8_CR14","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., et al.: Parameterized Algorithms. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-21275-3"},{"key":"8_CR15","doi-asserted-by":"publisher","unstructured":"Cygan, M., Hajiaghayi, M., Khuller, S.: LP rounding for k-centers with non-uniform hard capacities. In: 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science (FOCS), pp. 273\u2013282. IEEE (2012). https:\/\/doi.org\/10.1109\/FOCS.2012.63","DOI":"10.1109\/FOCS.2012.63"},{"key":"8_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1007\/11611257_21","volume-title":"SOFSEM 2006: Theory and Practice of Computer Science","author":"F Dehne","year":"2006","unstructured":"Dehne, F., Fellows, M., Fernau, H., Prieto, E., Rosamond, F.: nonblocker: parameterized algorithmics for minimum dominating set. In: Wiedermann, J., Tel, G., Pokorn\u00fd, J., Bielikov\u00e1, M., \u0160tuller, J. (eds.) SOFSEM 2006. LNCS, vol. 3831, pp. 237\u2013245. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11611257_21"},{"key":"8_CR17","doi-asserted-by":"publisher","unstructured":"Demirci, H.G., Li, S.: Constant approximation for capacitated k-median with $$(1+\\epsilon )$$-capacity violation. In: 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, Rome, Italy, 11\u201315 July 2016, pp. 73:1\u201373:14 (2016). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2016.73","DOI":"10.4230\/LIPIcs.ICALP.2016.73"},{"key":"8_CR18","first-page":"128","volume":"23","author":"I Dinur","year":"2016","unstructured":"Dinur, I.: Mildly exponential reduction from gap 3SAT to polynomial-gap label-cover. Electron. Colloquium Comput. Complex. (ECCC) 23, 128 (2016)","journal-title":"Electron. Colloquium Comput. Complex. (ECCC)"},{"key":"8_CR19","doi-asserted-by":"publisher","unstructured":"Fakcharoenphol, J., Rao, S., Talwar, K.: A tight bound on approximating arbitrary metrics by tree metrics. In: Proceedings of the 35th Annual ACM Symposium on Theory of Computing, San Diego, CA, USA, 9\u201311 June 2003, pp. 448\u2013455 (2003). https:\/\/doi.org\/10.1145\/780542.780608","DOI":"10.1145\/780542.780608"},{"issue":"6","key":"8_CR20","doi-asserted-by":"publisher","first-page":"146","DOI":"10.3390\/a13060146","volume":"13","author":"AE Feldmann","year":"2020","unstructured":"Feldmann, A.E., Karthik, C., Lee, E., Manurangsi, P.: A survey on approximation in parameterized complexity: hardness and algorithms. Algorithms 13(6), 146 (2020). https:\/\/doi.org\/10.3390\/a13060146","journal-title":"Algorithms"},{"issue":"1","key":"8_CR21","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). https:\/\/doi.org\/10.1006\/jagm.1998.0993","journal-title":"J. Algorithms"},{"key":"8_CR22","doi-asserted-by":"publisher","unstructured":"Gupta, A., Lee, E., Li, J.: An FPT algorithm beating 2-approximation for k-cut. In: Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2821\u20132837. Society for Industrial and Applied Mathematics (2018). https:\/\/doi.org\/10.1137\/1.9781611975031.179","DOI":"10.1137\/1.9781611975031.179"},{"issue":"1","key":"8_CR23","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1006\/jagm.2000.1100","volume":"37","author":"MR Korupolu","year":"2000","unstructured":"Korupolu, M.R., Plaxton, C.G., Rajaraman, R.: Analysis of a local search heuristic for facility location problems. J. Algorithms 37(1), 146\u2013188 (2000). https:\/\/doi.org\/10.1006\/jagm.2000.1100","journal-title":"J. Algorithms"},{"key":"8_CR24","doi-asserted-by":"publisher","unstructured":"Li, S.: On uniform capacitated $$k$$-median beyond the natural $$\\text{LP}$$ relaxation. In: Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 696\u2013707. SIAM (2015). https:\/\/doi.org\/10.1145\/2983633","DOI":"10.1145\/2983633"},{"key":"8_CR25","doi-asserted-by":"publisher","unstructured":"Li, S.: Approximating capacitated k-median with $$(1 + \\epsilon )k$$ open facilities. In: Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 786\u2013796. SIAM (2016). https:\/\/doi.org\/10.1137\/1.9781611974331.ch56","DOI":"10.1137\/1.9781611974331.ch56"},{"key":"8_CR26","doi-asserted-by":"publisher","unstructured":"Lokshtanov, D., Panolan, F., Ramanujan, M.S., Saurabh, S.: Lossy kernelization. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, pp. 224\u2013237. Association for Computing Machinery, New York, NY, USA (2017). https:\/\/doi.org\/10.1145\/3055399.3055456","DOI":"10.1145\/3055399.3055456"},{"key":"8_CR27","doi-asserted-by":"publisher","unstructured":"Lokshtanov, D., Ramanujan, M.S., Saurabh, S., Zehavi, M.: Parameterized complexity and approximability of directed odd cycle transversal. In: Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, 5\u20138 January 2020, pp. 2181\u20132200 (2020). https:\/\/doi.org\/10.1137\/1.9781611975994.134","DOI":"10.1137\/1.9781611975994.134"},{"key":"8_CR28","doi-asserted-by":"publisher","unstructured":"Manurangsi, P.: Tight running time lower bounds for strong inapproximability of maximum k-coverage, unique set cover and related problems (via t-wise agreement testing theorem). In: Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 62\u201381. SIAM (2020). https:\/\/doi.org\/10.1137\/1.9781611975994.5","DOI":"10.1137\/1.9781611975994.5"},{"key":"8_CR29","doi-asserted-by":"publisher","unstructured":"Manurangsi, P., Raghavendra, P.: A birthday repetition theorem and complexity of approximating dense CSPs. In: ICALP, pp. 78:1\u201378:15 (2017). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2017.78","DOI":"10.4230\/LIPIcs.ICALP.2017.78"},{"key":"8_CR30","doi-asserted-by":"crossref","unstructured":"van Rooij, J.M.: Exact Exponential-Time Algorithms for Domination Problems in Graphs. BOXpress (2011)","DOI":"10.1007\/s00453-011-9546-x"},{"issue":"3","key":"8_CR31","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(3), 709\u2013722 (2020). https:\/\/doi.org\/10.1007\/s11081-020-09503-0","journal-title":"Optim. Eng."}],"container-title":["Lecture Notes in Computer Science","Approximation and Online Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-80879-2_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,12,1]],"date-time":"2021-12-01T22:04:57Z","timestamp":1638396297000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-80879-2_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030808785","9783030808792"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-80879-2_8","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":"6 July 2021","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":"2020","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"9 September 2020","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10 September 2020","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"waoa2020","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/algo2020.di.unipi.it\/WAOA2020\/index.html","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":"40","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":"15","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":"0","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":"38% - 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.125","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":"5.95","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)"}}]}}