{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T15:54:15Z","timestamp":1776786855667,"version":"3.51.2"},"publisher-location":"Cham","reference-count":21,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319038971","type":"print"},{"value":"9783319038988","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-319-03898-8_11","type":"book-chapter","created":{"date-parts":[[2013,11,19]],"date-time":"2013-11-19T07:57:26Z","timestamp":1384847846000},"page":"110-122","source":"Crossref","is-referenced-by-count":18,"title":["Fixed-Parameter and Approximation Algorithms: A New Look"],"prefix":"10.1007","author":[{"given":"Rajesh","family":"Chitnis","sequence":"first","affiliation":[]},{"given":"MohammadTaghi","family":"Hajiaghayi","sequence":"additional","affiliation":[]},{"given":"Guy","family":"Kortsarz","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"11_CR1","unstructured":"Arora, S., Lund, C.: Approximation algorithms for NP-hard problems. In: Hochbaum, D. (ed.) PWS Publishing Co., Boston (1997)"},{"key":"11_CR2","doi-asserted-by":"crossref","unstructured":"Bellare, M., Goldwasser, S., Lund, C., Russeli, A.: Efficient probabilistically checkable proofs and applications to approximations. In: STOC (1993)","DOI":"10.1145\/167088.167174"},{"issue":"1","key":"11_CR3","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1093\/comjnl\/bxm086","volume":"51","author":"L. Cai","year":"2008","unstructured":"Cai, L.: Parameterized complexity of cardinality constrained optimization problems. Comput. J.\u00a051(1), 102\u2013121 (2008)","journal-title":"Comput. J."},{"key":"11_CR4","doi-asserted-by":"crossref","unstructured":"Downey, R., Fellows, M.: Parameterized Complexity. Springer (1999)","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"11_CR5","doi-asserted-by":"crossref","unstructured":"Dreyfus, S.E., Wagner, R.A.: The steiner problem in graphs. Networks\u00a01(3) (1971)","DOI":"10.1002\/net.3230010302"},{"issue":"6","key":"11_CR6","first-page":"26","volume":"2","author":"M.R. Fellows","year":"2012","unstructured":"Fellows, M.R., Guo, J., Marx, D., Saurabh, S.: Data Reduction and Problem Kernels (Dagstuhl Seminar 12241). Dagstuhl Reports\u00a02(6), 26\u201350 (2012)","journal-title":"Dagstuhl Reports"},{"issue":"2","key":"11_CR7","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1137\/100794560","volume":"25","author":"J. Guo","year":"2011","unstructured":"Guo, J., Niedermeier, R., Such\u00fd, O.: Parameterized complexity of arc-weighted directed steiner problems. SIAM J. Discrete Math.\u00a025(2), 583\u2013599 (2011)","journal-title":"SIAM J. Discrete Math."},{"key":"11_CR8","unstructured":"Gupta, A.: Improved results for directed multicut. In: SODA, pp. 454\u2013455 (2003)"},{"key":"11_CR9","doi-asserted-by":"publisher","first-page":"585","DOI":"10.1145\/780542.780628","volume-title":"STOC 2003: Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing","author":"E. Halperin","year":"2003","unstructured":"Halperin, E., Krauthgamer, R.: Polylogarithmic inapproximability. In: STOC 2003: Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, pp. 585\u2013594. ACM Press, New York (2003)"},{"key":"11_CR10","unstructured":"H\u00e5stad, J.: Clique is hard to approximate within n 1\u2009\u2212\u2009\u03b5 . In: FOCS (1996)"},{"key":"11_CR11","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Paturi, R.: On the complexity of k-sat. J. Comput. Syst. Sci.\u00a062(2) (2001)","DOI":"10.1006\/jcss.2000.1727"},{"key":"11_CR12","doi-asserted-by":"crossref","unstructured":"Khot, S.: On the Unique Games Conjecture. In: FOCS, p. 3 (2005)","DOI":"10.1109\/SFCS.2005.61"},{"issue":"5","key":"11_CR13","doi-asserted-by":"publisher","first-page":"960","DOI":"10.1145\/185675.306789","volume":"41","author":"C. Lund","year":"1994","unstructured":"Lund, C., Yannakakis, M.: On the hardness of approximating minimization problems. J. ACM\u00a041(5), 960\u2013981 (1994)","journal-title":"J. ACM"},{"key":"11_CR14","doi-asserted-by":"crossref","unstructured":"Marx, D.: Parameterized complexity and approximation algorithms. Comput. J.\u00a051(1) (2008)","DOI":"10.1093\/comjnl\/bxm048"},{"key":"11_CR15","doi-asserted-by":"crossref","unstructured":"Marx, D.: Completely inapproximable monotone and antimonotone parameterized problems. Journal of Computer and System Sciences\u00a079(1) (2013)","DOI":"10.1016\/j.jcss.2012.09.001"},{"issue":"20","key":"11_CR16","doi-asserted-by":"publisher","first-page":"1161","DOI":"10.1016\/j.ipl.2009.07.016","volume":"109","author":"D. Marx","year":"2009","unstructured":"Marx, D., Razgon, I.: Constant ratio fixed-parameter approximation of the edge multicut problem. Inf. Process. Lett.\u00a0109(20), 1161\u20131166 (2009)","journal-title":"Inf. Process. Lett."},{"key":"11_CR17","doi-asserted-by":"crossref","unstructured":"Marx, D., Razgon, I.: Fixed-parameter tractability of multicut parameterized by the size of the cutset. In: STOC, pp. 469\u2013478 (2011)","DOI":"10.1145\/1993636.1993699"},{"key":"11_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"276","DOI":"10.1007\/978-3-642-32512-0_24","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"D. Moshkovitz","year":"2012","unstructured":"Moshkovitz, D.: The Projection Games Conjecture and The NP-Hardness of ln n-Approximating Set-Cover. In: Gupta, A., Jansen, K., Rolim, J., Servedio, R. (eds.) APPROX\/RANDOM 2012. LNCS, vol.\u00a07408, pp. 276\u2013287. Springer, Heidelberg (2012)"},{"key":"11_CR19","doi-asserted-by":"crossref","unstructured":"Moshkovitz, D., Raz, R.: Two-query PCP with subconstant error. J. ACM\u00a057(5) (2010)","DOI":"10.1145\/1754399.1754402"},{"issue":"8","key":"11_CR20","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1016\/j.jcss.2009.04.002","volume":"75","author":"I. Razgon","year":"2009","unstructured":"Razgon, I., O\u2019Sullivan, B.: Almost 2-sat is fixed-parameter tractable. J. Comput. Syst. Sci.\u00a075(8), 435\u2013450 (2009)","journal-title":"J. Comput. Syst. Sci."},{"key":"11_CR21","doi-asserted-by":"crossref","unstructured":"Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. In: STOC, pp. 681\u2013690 (2006)","DOI":"10.1145\/1132516.1132612"}],"container-title":["Lecture Notes in Computer Science","Parameterized and Exact Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-03898-8_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,30]],"date-time":"2025-04-30T21:17:05Z","timestamp":1746047825000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-03898-8_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783319038971","9783319038988"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-03898-8_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013]]}}}