{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,7]],"date-time":"2025-10-07T00:17:44Z","timestamp":1759796264847,"version":"build-2065373602"},"reference-count":48,"publisher":"Springer Science and Business Media LLC","issue":"12","license":[{"start":{"date-parts":[[2025,8,13]],"date-time":"2025-08-13T00:00:00Z","timestamp":1755043200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,8,13]],"date-time":"2025-08-13T00:00:00Z","timestamp":1755043200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["2313372","2236669"],"award-info":[{"award-number":["2313372","2236669"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000893","name":"Simons Foundation","doi-asserted-by":"publisher","award":["825876"],"award-info":[{"award-number":["825876"]}],"id":[{"id":"10.13039\/100000893","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006785","name":"Google","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006785","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2025,12]]},"DOI":"10.1007\/s00453-025-01338-4","type":"journal-article","created":{"date-parts":[[2025,8,13]],"date-time":"2025-08-13T04:01:20Z","timestamp":1755057680000},"page":"1711-1731","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On Equivalence of Parameterized Inapproximability of k-Median, k-Max-Coverage, and 2-CSP"],"prefix":"10.1007","volume":"87","author":[{"given":"Karthik","family":"C.S.","sequence":"first","affiliation":[]},{"given":"Euiwoong","family":"Lee","sequence":"additional","affiliation":[]},{"given":"Pasin","family":"Manurangsi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,8,13]]},"reference":[{"issue":"3","key":"1338_CR1","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1145\/278298.278306","volume":"45","author":"S Arora","year":"1998","unstructured":"Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof verification and the hardness of approximation problems. J. ACM 45(3), 501\u2013555 (1998)","journal-title":"J. ACM"},{"issue":"1","key":"1338_CR2","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1145\/273865.273901","volume":"45","author":"S Arora","year":"1998","unstructured":"Arora, S., Safra, S.: Probabilistic checking of proofs: A new characterization of NP. J. ACM 45(1), 70\u2013122 (1998)","journal-title":"J. ACM"},{"issue":"3","key":"1338_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3444942","volume":"68","author":"A Bhattacharyya","year":"2021","unstructured":"Bhattacharyya, A., Bonnet, \u00c9., Egri, L., Ghoshal, S., Karthik, C.S., Lin, B., Manurangsi, P., Marx, D.: Parameterized intractability of even set and shortest vector problem. J. ACM 68(3), 1\u201316 (2021)","journal-title":"J. ACM"},{"key":"1338_CR4","doi-asserted-by":"crossref","unstructured":"Bennett, H., Cheraghchi, M., Guruswami, V., Ribeiro, J.: Parameterized inapproximability of the minimum distance problem over all fields and the shortest vector problem in all lp norms. In Barna Saha and Rocco\u00a0A. Servedio, editors, Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023, pages 553\u2013566. ACM (2023)","DOI":"10.1145\/3564246.3585214"},{"key":"1338_CR5","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, July 9-13, 2018, Prague, Czech Republic, pages 17:1\u201317:15 (2018)"},{"key":"1338_CR6","doi-asserted-by":"crossref","unstructured":"Bukh, B., Karthik C.S., Narayanan, B.: Applications of random algebraic constructions to hardness of approximation. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022, pages 237\u2013244. IEEE (2021)","DOI":"10.1109\/FOCS52979.2021.00032"},{"issue":"4","key":"1338_CR7","doi-asserted-by":"publisher","first-page":"772","DOI":"10.1137\/18M1166869","volume":"49","author":"P Chalermsook","year":"2020","unstructured":"Chalermsook, P., Cygan, M., Kortsarz, G., Laekhanukit, B., Manurangsi, P., Nanongkai, D., Trevisan, L.: From gap-exponential time hypothesis to fixed parameter tractable inapproximability: Clique, dominating set, and more. SIAM J. Comput. 49(4), 772\u2013810 (2020)","journal-title":"SIAM J. Comput."},{"issue":"6","key":"1338_CR8","doi-asserted-by":"publisher","first-page":"1740","DOI":"10.1137\/080733991","volume":"40","author":"G Calinescu","year":"2011","unstructured":"Calinescu, G., Chekuri, C., P\u00e1l, M., Vondr\u00e1k, J.: Maximizing a monotone submodular function subject to a matroid constraint. SIAM J. Comput. 40(6), 1740\u20131766 (2011)","journal-title":"SIAM J. Comput."},{"key":"1338_CR9","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Saurabh, S.: Parameterized algorithms. Springer, Cham (2015)"},{"key":"1338_CR10","unstructured":"Chen, Y., Feng, Y., Laekhanukit, B., Liu, Y.: Simple combinatorial construction of the $$k^{\\text{o(1)}}$$-lower bound for approximating the parameterized k-clique. CoRR, abs\/2304.07516 (2023)"},{"issue":"2","key":"1338_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3447584","volume":"17","author":"R Chitnis","year":"2021","unstructured":"Chitnis, R., Feldmann, A.E., Manurangsi, P.: Parameterized approximation algorithms for bidirected Steiner network problems. ACM Trans. Algorithms (TALG) 17(2), 1\u201368 (2021)","journal-title":"ACM Trans. Algorithms (TALG)"},{"issue":"8","key":"1338_CR12","doi-asserted-by":"publisher","first-page":"3200","DOI":"10.1007\/s00453-019-00580-x","volume":"81","author":"R Chitnis","year":"2019","unstructured":"Chitnis, R., Feldmann, A.E., Such\u00fd, O.: A tight lower bound for planar Steiner orientation. Algorithmica 81(8), 3200\u20133216 (2019)","journal-title":"Algorithmica"},{"key":"1338_CR13","unstructured":"Cohen-Addad, V., Gupta, A., Kumar, A., Lee, E., Li, J.: Tight FPT Approximations for k-Median and k-Means. In Christel B., Ioannis C., Paola F., Stefano L. (eds.) 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132 of Leibniz International Proceedings in Informatics (LIPIcs), pages 42:1\u201342:14, Dagstuhl, Germany, (2019). Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik"},{"key":"1338_CR14","doi-asserted-by":"crossref","unstructured":"Cohen-Addad, 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), pages 940\u2013986. SIAM (2023)","DOI":"10.1137\/1.9781611977554.ch37"},{"issue":"2","key":"1338_CR15","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1137\/17M1127211","volume":"48","author":"Y Chen","year":"2019","unstructured":"Chen, Y., Lin, B.: The constant inapproximability of the parameterized dominating set problem. SIAM J. Comput. 48(2), 513\u2013533 (2019)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"1338_CR16","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1006\/inco.2000.3011","volume":"167","author":"P Crescenzi","year":"2001","unstructured":"Crescenzi, P., Silvestri, R., Trevisan, L.: On weighted vs unweighted versions of combinatorial optimization problems. Inf. Comput. 167(1), 10\u201326 (2001)","journal-title":"Inf. Comput."},{"key":"1338_CR17","doi-asserted-by":"crossref","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer (2013)","DOI":"10.1007\/978-1-4471-5559-1"},{"issue":"4","key":"1338_CR18","doi-asserted-by":"publisher","first-page":"902","DOI":"10.1007\/s00453-022-01052-5","volume":"85","author":"P Dvo\u0159\u00e1k","year":"2022","unstructured":"Dvo\u0159\u00e1k, P., Feldmann, A.E., Rai, A., Rza\u017cewski, P.: Parameterized inapproximability of independent set in H-free graphs. Algorithmica 85(4), 902\u2013928 (2022)","journal-title":"Algorithmica"},{"issue":"3","key":"1338_CR19","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"},{"key":"1338_CR20","unstructured":"Dinur, I.: Mildly exponential reduction from gap 3sat to polynomial-gap label-cover. Electronic Colloquium on Computational Complexity (ECCC) (2016)"},{"issue":"4","key":"1338_CR21","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)"},{"issue":"2","key":"1338_CR22","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1145\/226643.226652","volume":"43","author":"U Feige","year":"1996","unstructured":"Feige, U., Goldwasser, S., Lov\u00e1sz, L., Safra, S., Szegedy, M.: Interactive proofs and the hardness of approximating cliques. J. ACM 43(2), 268\u2013292 (1996)","journal-title":"J. ACM"},{"issue":"6","key":"1338_CR23","doi-asserted-by":"publisher","first-page":"146","DOI":"10.3390\/a13060146","volume":"13","author":"AE Feldmann","year":"2020","unstructured":"Feldmann, A.E., Karthik, C.S., Lee, E., Manurangsi, P.: A survey on approximation in parameterized complexity: Hardness and algorithms. Algorithms 13(6), 146 (2020)","journal-title":"Algorithms"},{"issue":"1","key":"1338_CR24","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"},{"key":"1338_CR25","doi-asserted-by":"crossref","unstructured":"Guruswami, V., Lin, B., Ren, X., Sun, Y., Wu, K.: Almost optimal time lower bound for approximating parameterized clique, csp, and more, under ETH. CoRR, abs\/2404.08870 (2024)","DOI":"10.1145\/3717823.3718130"},{"key":"1338_CR26","doi-asserted-by":"crossref","unstructured":"Guruswami, V., Lin, B., Ren, X., Sun, Y., Wu, K.: Parameterized inapproximability hypothesis under ETH. In STOC (2024)","DOI":"10.1145\/3749982"},{"issue":"2","key":"1338_CR27","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1145\/261342.571216","volume":"28","author":"DS Hochba","year":"1997","unstructured":"Hochba, D.S.: Approximation algorithms for NP-hard problems. ACM SIGACT News 28(2), 40\u201352 (1997)","journal-title":"ACM SIGACT News"},{"issue":"2","key":"1338_CR28","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":"1338_CR29","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":"1338_CR30","doi-asserted-by":"crossref","unstructured":"Khot, S.: On the power of unique 2-prover 1-round games. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pages 767\u2013775. ACM (2002)","DOI":"10.1145\/509907.510017"},{"key":"1338_CR31","unstructured":"Karthik, C.S., Khot, S.: Almost polynomial factor inapproximability for parameterized k-clique. In Shachar L. (ed.) 37th Computational Complexity Conference, CCC 2022, July 20-23, 2022, Philadelphia, PA, USA, volume 234 of LIPIcs, pages 6:1\u20136:21. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2022)"},{"key":"1338_CR32","doi-asserted-by":"crossref","unstructured":"Kolmogorov, V., Krokhin, A.A., Rol\u00ednek, M.: The complexity of general-valued CSPs. In Venkatesan G. (ed.) IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 1246\u20131258. IEEE Computer Society (2015)","DOI":"10.1109\/FOCS.2015.80"},{"issue":"5","key":"1338_CR33","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3325116","volume":"66","author":"CS Karthik","year":"2019","unstructured":"Karthik, C.S., Laekhanukit, B., Manurangsi, P.: On the parameterized complexity of approximating dominating set. J. ACM 66(5), 1\u201338 (2019)","journal-title":"J. ACM"},{"issue":"4","key":"1338_CR34","doi-asserted-by":"publisher","first-page":"539","DOI":"10.1007\/s00493-019-4113-1","volume":"40","author":"CS Karthik","year":"2020","unstructured":"Karthik, C.S., Manurangsi, P.: On closest pair in Euclidean metric: Monochromatic is as hard as bichromatic. Combinatorica 40(4), 539\u2013573 (2020)","journal-title":"Combinatorica"},{"issue":"2\u20133","key":"1338_CR35","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/j.comgeo.2004.03.003","volume":"28","author":"T Kanungo","year":"2004","unstructured":"Kanungo, T., Mount, D.M., Netanyahu, N.S., Piatko, C.D., Silverman, R., Wu, A.Y.: A local search approximation algorithm for k-means clustering. Comput. Geom. 28(2\u20133), 89\u2013112 (2004)","journal-title":"Comput. Geom."},{"key":"1338_CR36","doi-asserted-by":"crossref","unstructured":"Khot, S., Minzer, D., Safra, M.: On independent sets, 2-to-2 games, and Grassmann graphs. In Hamed H., Pierre M., Valerie K. (eds.) Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 576\u2013589. ACM (2017)","DOI":"10.1145\/3055399.3055432"},{"key":"1338_CR37","doi-asserted-by":"crossref","unstructured":"Khot, S., Minzer, D., Safra, M.: Pseudorandom sets in Grassmann graph have near-perfect expansion. In Mikkel T. (ed.) 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 592\u2013601. IEEE Computer Society (2018)","DOI":"10.1109\/FOCS.2018.00062"},{"key":"1338_CR38","doi-asserted-by":"crossref","unstructured":"Karthik, C.S., Navon, I.L.: On hardness of approximation of parameterized set cover and label cover: Threshold graphs from error correcting codes. In Hung\u00a0Viet L., Valerie K. (eds.) 4th Symposium on Simplicity in Algorithms, SOSA 2021, Virtual Conference, January 11-12, 2021, pages 210\u2013223. SIAM (2021)","DOI":"10.1137\/1.9781611976472.24"},{"issue":"5","key":"1338_CR39","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3212622","volume":"65","author":"B Lin","year":"2018","unstructured":"Lin, B.: The parameterized complexity of the k-biclique problem. J. ACM 65(5), 1\u201323 (2018)","journal-title":"J. ACM"},{"key":"1338_CR40","unstructured":"Lin, B.: A simple gap-producing reduction for the parameterized set cover problem. In 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, pages:1\u201315 (2019)"},{"key":"1338_CR41","doi-asserted-by":"crossref","unstructured":"Lin, B.: Constant approximating k-clique is W[1]-hard. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 1749\u20131756, (2021)","DOI":"10.1145\/3406325.3451016"},{"key":"1338_CR42","doi-asserted-by":"crossref","unstructured":"Lin, B., Ren, X., Sun, Y., Wang, X.: Constant approximating parameterized k-setcover is W[2]-hard. In Nikhil B., Viswanath N. (eds.) Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023, pages 3305\u20133316. SIAM (2023)","DOI":"10.1137\/1.9781611977554.ch126"},{"key":"1338_CR43","doi-asserted-by":"crossref","unstructured":"Lin, B., Ren, X., Sun, Y., Wang, X.: Improved hardness of approximating k-clique under ETH. In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, November 6-9, 2023, pages 285\u2013306. IEEE (2023)","DOI":"10.1109\/FOCS57990.2023.00025"},{"key":"1338_CR44","doi-asserted-by":"crossref","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, January 5-8, 2020, pages 2181\u20132200 (2020)","DOI":"10.1137\/1.9781611975994.134"},{"key":"1338_CR45","doi-asserted-by":"crossref","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 Shuchi C. (ed.) Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 62\u201381. SIAM (2020)","DOI":"10.1137\/1.9781611975994.5"},{"key":"1338_CR46","unstructured":"Manurangsi, P., Raghavendra, P.: A birthday repetition theorem and complexity of approximating dense csps. CoRR, abs\/1607.02986 (2016)"},{"key":"1338_CR47","unstructured":"Ohsaka, N.: On the parameterized intractability of determinant maximization. arXiv preprint arXiv:2209.12519 (2022)"},{"key":"1338_CR48","unstructured":"Wlodarczyk, M.: Inapproximability within W[1]: the case of Steiner orientation. CoRR, abs\/1907.06529 (2019)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01338-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-025-01338-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01338-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,6]],"date-time":"2025-10-06T08:08:07Z","timestamp":1759738087000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-025-01338-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,8,13]]},"references-count":48,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2025,12]]}},"alternative-id":["1338"],"URL":"https:\/\/doi.org\/10.1007\/s00453-025-01338-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2025,8,13]]},"assertion":[{"value":"15 October 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 July 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 August 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}