{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,7]],"date-time":"2025-11-07T13:17:44Z","timestamp":1762521464888},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2012,5]]},"DOI":"10.1007\/s00224-011-9366-z","type":"journal-article","created":{"date-parts":[[2011,10,13]],"date-time":"2011-10-13T06:48:15Z","timestamp":1318488495000},"page":"641-674","source":"Crossref","is-referenced-by-count":3,"title":["Structure of Polynomial-Time Approximation"],"prefix":"10.1007","volume":"50","author":[{"given":"Erik Jan","family":"van Leeuwen","sequence":"first","affiliation":[]},{"given":"Jan","family":"van Leeuwen","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,10,14]]},"reference":[{"issue":"3","key":"9366_CR1","doi-asserted-by":"crossref","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"},{"key":"9366_CR2","volume-title":"Complexity and Approximation\u2014Combinatorial Optimization Problems and Their Approximation Properties","author":"G. Ausiello","year":"1999","unstructured":"Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.: Complexity and Approximation\u2014Combinatorial Optimization Problems and Their Approximation Properties. Springer, Berlin (1999)"},{"key":"9366_CR3","unstructured":"Bazgan, C.: Sch\u00e9mas d\u2019approximation et complexit\u00e9 param\u00e9tr\u00e9e, Rapport de\u00a0stage de\u00a0DEA d\u2019Informatique, Universit\u00e9 Paris-Sud, Orsay (1995)"},{"issue":"3","key":"9366_CR4","doi-asserted-by":"crossref","first-page":"465","DOI":"10.1006\/jcss.1997.1490","volume":"54","author":"L. Cai","year":"1997","unstructured":"Cai, L., Chen, J.: On fixed-parameter complexity and approximability of NP optimization problems. J. Comput. Syst. Sci. 54(3), 465\u2013474 (1997)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"9366_CR5","doi-asserted-by":"crossref","first-page":"459","DOI":"10.1007\/s00224-007-1346-y","volume":"41","author":"L. Cai","year":"2007","unstructured":"Cai, L., Fellows, M., Juedes, D., Rosamond, F.: The complexity of polynomial-time approximation. Theory Comput. Syst. 41(3), 459\u2013477 (2007)","journal-title":"Theory Comput. Syst."},{"issue":"4","key":"9366_CR6","doi-asserted-by":"crossref","first-page":"789","DOI":"10.1016\/S0022-0000(03)00074-6","volume":"67","author":"L. Cai","year":"2003","unstructured":"Cai, L., Juedes, D.: On the existence of subexponential parameterized algorithms. J. Comput. Syst. Sci. 67(4), 789\u2013807 (2003)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"9366_CR7","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/S0020-0190(97)00164-6","volume":"64","author":"M. Cesati","year":"1997","unstructured":"Cesati, M., Trevisan, L.: On the efficiency of polynomial time approximation schemes. Inf. Process. Lett. 64(4), 165\u2013171 (1997)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"9366_CR8","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1016\/j.dam.2006.04.040","volume":"155","author":"J. Chen","year":"2007","unstructured":"Chen, J., Huang, X., Kanj, I.A., Xia, G.: Polynomial time approximation schemes and parameterized complexity. Discrete Appl. Math. 155(2), 180\u2013193 (2007)","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"9366_CR9","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1142\/S0129054191000133","volume":"2","author":"Z.-Z. Chen","year":"1991","unstructured":"Chen, Z.-Z., Toda, S.: On the complexity of computing optimal solutions. Int. J. Found. Comput. Sci. 2(3), 207\u2013220 (1991)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"4","key":"9366_CR10","first-page":"203","volume":"4","author":"N. Chiba","year":"1981","unstructured":"Chiba, N., Nishizeki, T., Saito, N.: Applications of the Lipton and Tarjan\u2019s planar separator theorem. J. Inf. Process. 4(4), 203\u2013207 (1981)","journal-title":"J. Inf. Process."},{"key":"9366_CR11","first-page":"46","volume-title":"Approximation Algorithms for NP-Hard Problems","author":"E.G. Coffman Jr.","year":"1997","unstructured":"Coffman, E.G. Jr., Garey, M.G., Johnson, D.S.: Approximation algorithms for bin packing: a survey. In: Hochbaum, D.S. (ed.) Approximation Algorithms for NP-Hard Problems, pp.\u00a046\u201393. PWS Publishing Company, Boston (1997)"},{"issue":"1","key":"9366_CR12","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1007\/s10951-006-5594-5","volume":"9","author":"E.G. Coffman Jr.","year":"2006","unstructured":"Coffman, E.G. Jr., Lueker, G.S.: Approximation algorithms for extensible bin packing. J. Sched. 9(1), 63\u201369 (2006)","journal-title":"J. Sched."},{"issue":"5","key":"9366_CR13","doi-asserted-by":"crossref","first-page":"1759","DOI":"10.1137\/S0097539796304220","volume":"28","author":"P. Crescenzi","year":"1999","unstructured":"Crescenzi, P., Kann, V., Silvestre, R., Trevisan, L.: Structure in approximation classes. SIAM J. Comput. 28(5), 1759\u20131782 (1999)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"9366_CR14","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1016\/0890-5401(91)90025-W","volume":"93","author":"P. Crescenzi","year":"1991","unstructured":"Crescenzi, P., Panconesi, A.: Completeness in approximation classes. Inf. Comput. 93(2), 241\u2013262 (1991)","journal-title":"Inf. Comput."},{"issue":"1","key":"9366_CR15","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s002249910001","volume":"33","author":"P. Crescenzi","year":"2000","unstructured":"Crescenzi, P., Trevisan, L.: On approximation scheme preserving reducibility and its applications. Theory Comput. Syst. 33(1), 1\u201316 (2000)","journal-title":"Theory Comput. Syst."},{"issue":"2","key":"9366_CR16","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1016\/j.jcss.2003.12.001","volume":"69","author":"E.D. Demaine","year":"2004","unstructured":"Demaine, E.D., Hajiaghayi, M., Nishimura, N., Ragde, P., Thilikos, D.M.: Approximation algorithms for classes of graphs excluding single-crossing graphs as minors. J. Comput. Syst. Sci. 69(2), 166\u2013195 (2004)","journal-title":"J. Comput. Syst. Sci."},{"key":"9366_CR17","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, New York (1999)"},{"key":"9366_CR18","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Berlin (2006)"},{"issue":"3","key":"9366_CR19","doi-asserted-by":"crossref","first-page":"409","DOI":"10.1006\/jagm.1994.1042","volume":"17","author":"M. F\u00fcrer","year":"1994","unstructured":"F\u00fcrer, M., Raghavachari, B.: Approximating the minimum-degree steiner tree to within one of optimal. J. Algorithms 17(3), 409\u2013423 (1994)","journal-title":"J. Algorithms"},{"issue":"3","key":"9366_CR20","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1145\/322077.322090","volume":"25","author":"M.R. Garey","year":"1976","unstructured":"Garey, M.R., Johnson, D.S.: \u2018Strong\u2019 NP-completeness results: motivation, examples, and implications. J. ACM 25(3), 499\u2013508 (1976)","journal-title":"J. ACM"},{"key":"9366_CR21","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco (1979)"},{"issue":"1","key":"9366_CR22","doi-asserted-by":"crossref","first-page":"144","DOI":"10.1145\/7531.7535","volume":"34","author":"D.S. Hochbaum","year":"1987","unstructured":"Hochbaum, D.S., Shmoys, D.B.: Using dual approximation algorithms for scheduling problems: theoretical and practical results. J. ACM 34(1), 144\u2013162 (1987)","journal-title":"J. ACM"},{"key":"9366_CR23","unstructured":"Huang, X.: Parameterized complexity and polynomial-time approximation schemes, Ph.D. Thesis, Texas A&M University (2004)"},{"issue":"2","key":"9366_CR24","doi-asserted-by":"crossref","first-page":"238","DOI":"10.1006\/jagm.1997.0903","volume":"26","author":"D.B. Hunt III","year":"1998","unstructured":"Hunt, D.B. III, Marathe, M.V., Radhakrishnan, V., Ravi, S.S., Rosenkrantz, D.J., Stearns, R.E.: NC-approximation schemes for NP- and PSPACE-hard problems for geometric graphs. J.\u00a0Algorithms 26(2), 238\u2013274 (1998)","journal-title":"J.\u00a0Algorithms"},{"key":"9366_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"362","DOI":"10.1007\/978-3-540-27810-8_31","volume-title":"Algorithm Theory\u2014SWAT 2004, Proc. 9th Scandinavian Workshop","author":"K. Jansen","year":"2004","unstructured":"Jansen, K., Zhang, G.: Maximizing the number of packed rectangles. In: Hagerup, T., Katajainen, J. (eds.) Algorithm Theory\u2014SWAT 2004, Proc. 9th Scandinavian Workshop. Lecture Notes in Computer Science, vol.\u00a03111, pp.\u00a0362\u2013371. Springer, Berlin (2004)"},{"key":"9366_CR26","unstructured":"Kann, V.: On the approximability of NP-complete optimization problems, Dissertation, Department of Numerical Analysis and Computing Science, Royal Institute of Technology, Stockholm, Sweden (1992)"},{"key":"9366_CR27","first-page":"312","volume-title":"Proceedings of the 23rd Annual IEEE Symposium on Foundations of Computer Science (FOCS)","author":"N. Karmarkar","year":"1982","unstructured":"Karmarkar, N., Karp, R.M.: An efficient approximation scheme for the one-dimensional bin packing problem. In: Proceedings of the 23rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp.\u00a0312\u2013320, IEEE Comput. Soc., Los Alamitos (1982)"},{"issue":"1","key":"9366_CR28","doi-asserted-by":"crossref","first-page":"164","DOI":"10.1137\/S0097539795286612","volume":"28","author":"S. Khanna","year":"1998","unstructured":"Khanna, S., Motwani, R., Sudan, M., Vazirani, U.V.: On syntactic versus computational views of approximability. SIAM J. Comput. 28(1), 164\u2013191 (1998)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"9366_CR29","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1006\/inco.1994.1100","volume":"115","author":"P.G. Kolaitis","year":"1994","unstructured":"Kolaitis, P.G., Thakur, M.N.: Logical definability of NP optimization problems. Inf. Comput. 115(2), 321\u2013353 (1994)","journal-title":"Inf. Comput."},{"issue":"3","key":"9366_CR30","doi-asserted-by":"crossref","first-page":"391","DOI":"10.1006\/jcss.1995.1031","volume":"50","author":"P.G. Kolaitis","year":"1995","unstructured":"Kolaitis, P.G., Thakur, M.N.: Approximation properties of NP minimization classes. J. Comput. Syst. Sci. 50(3), 391\u2013411 (1995)","journal-title":"J. Comput. Syst. Sci."},{"key":"9366_CR31","first-page":"601","volume-title":"26th International Symposium on Theoretical Aspects of Computer Science (STACS 2009)","author":"S. Kratsch","year":"2009","unstructured":"Kratsch, S.: Polynomial kernelizations for MIN F+\u03a01 and MAX NP. In: Albers, S., Marion, J.-Y. (eds.) 26th International Symposium on Theoretical Aspects of Computer Science (STACS 2009), Schloss Dagstuhl\u2014Leibniz-Zentrum fuer Informatik, Germany, pp.\u00a0601\u2013612 (2009)"},{"key":"9366_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"154","DOI":"10.1007\/11847250_14","volume-title":"Parameterized and Exact Computation\u2014IWPEC 2006, Proceedings of the Second International Workshop","author":"D. Marx","year":"2006","unstructured":"Marx, D.: Parameterized complexity of independence and domination on geometric graphs. In: Bodlaender, H.L., Langston, M.A. (eds.) Parameterized and Exact Computation\u2014IWPEC 2006, Proceedings of the Second International Workshop. Lecture Notes in Computer Science, vol.\u00a04169, pp.\u00a0154\u2013165. Springer, Berlin (2006)"},{"key":"9366_CR33","doi-asserted-by":"crossref","first-page":"338","DOI":"10.1109\/FOCS.2007.26","volume-title":"Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS)","author":"D. Marx","year":"2007","unstructured":"Marx, D.: On the optimality of planar and geometric approximation schemes. In: Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp.\u00a0338\u2013348, IEEE Comput. Soc., Los Alamitos (2007)"},{"key":"9366_CR34","unstructured":"Orponen, P., Mannila, H.: On approximation preserving reductions: complete problems and robust measures, Technical Report C-1987-28, Department of Computer Science, University of Helsinki (1987)"},{"issue":"3","key":"9366_CR35","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C. Papadimitriou","year":"1991","unstructured":"Papadimitriou, C., Yannakakis, M.: Optimization, approximation and complexity classes. J. Comput. Syst. Sci. 43(3), 425\u2013440 (1991)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"9366_CR36","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/0304-3975(81)90081-5","volume":"15","author":"A. Paz","year":"1981","unstructured":"Paz, A., Moran, S.: Non deterministic polynomial optimization problems and their approximations. Theor. Comput. Sci. 15(3), 251\u2013277 (1981)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"9366_CR37","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1007\/BF01202286","volume":"4","author":"E. Petrank","year":"1994","unstructured":"Petrank, E.: The hardness of approximation: gap location. Comput. Complex. 4(2), 133\u2013157 (1994)","journal-title":"Comput. Complex."},{"issue":"6","key":"9366_CR38","doi-asserted-by":"crossref","first-page":"1353","DOI":"10.1287\/opre.33.6.1353","volume":"33","author":"M. Queyranne","year":"1985","unstructured":"Queyranne, M.: Bounds for assembly line balancing heuristics. Oper. Res. 33(6), 1353\u20131359 (1985)","journal-title":"Oper. Res."},{"issue":"2","key":"9366_CR39","doi-asserted-by":"crossref","first-page":"294","DOI":"10.1137\/0403025","volume":"3","author":"H.U. Simon","year":"1990","unstructured":"Simon, H.U.: On approximate solutions for combinatorial optimization problems. SIAM J. Discrete Math. 3(2), 294\u2013310 (1990)","journal-title":"SIAM J. Discrete Math."},{"key":"9366_CR40","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1007\/11604686_31","volume-title":"Graph-Theoretic Concepts in Computer Science\u2014WG 2005, Proceedings of the 31st International Workshop","author":"E.J. Leeuwen van","year":"2005","unstructured":"van Leeuwen, E.J.: Approximation algorithms for unit disk graphs. In: Kratsch, D. (ed.) Graph-Theoretic Concepts in Computer Science\u2014WG 2005, Proceedings of the 31st International Workshop. Lecture Notes in Computer Science, vol.\u00a03787, pp.\u00a0351\u2013361. Springer, Berlin (2005)"},{"key":"9366_CR41","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"316","DOI":"10.1007\/11785293_30","volume-title":"Algorithm Theory\u2014SWAT 2006, Proceedings of the 10th Scandinavian Workshop","author":"E.J. Leeuwen van","year":"2006","unstructured":"van Leeuwen, E.J.: Better approximation schemes for disk graphs. In: Arge, L., Freivalds, R. (eds.) Algorithm Theory\u2014SWAT 2006, Proceedings of the 10th Scandinavian Workshop. Lecture Notes in Computer Science, vol.\u00a04059, pp.\u00a0316\u2013327. Springer, Berlin (2006)"},{"key":"9366_CR42","unstructured":"van Leeuwen, E.J.: Optimization and approximation on systems of geometric objects, Ph.D. Thesis, University of Amsterdam (2009)"},{"key":"9366_CR43","first-page":"25","volume":"3","author":"V.G. Vizing","year":"1964","unstructured":"Vizing, V.G.: Ob otsenke khromaticheskogo klassa p-grafa (Russian: On an estimate of the chromatic class of a p-graph). Diskretn. Anal. 3, 25\u201330 (1964)","journal-title":"Diskretn. Anal."},{"issue":"6","key":"9366_CR44","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1016\/S0020-0190(97)00179-8","volume":"64","author":"G. Woeginger","year":"1997","unstructured":"Woeginger, G.: There is no asymptotic PTAS for two-dimensional vector packing. Inf. Process. Lett. 64(6), 293\u2013297 (1997)","journal-title":"Inf. Process. Lett."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-011-9366-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,6,20]],"date-time":"2017-06-20T07:51:42Z","timestamp":1497945102000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-011-9366-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,10,14]]},"references-count":44,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2012,5]]}},"alternative-id":["9366"],"URL":"https:\/\/doi.org\/10.1007\/s00224-011-9366-z","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,10,14]]}}}