{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T21:36:11Z","timestamp":1725572171695},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540228233"},{"type":"electronic","value":"9783540286295"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-28629-5_38","type":"book-chapter","created":{"date-parts":[[2010,12,17]],"date-time":"2010-12-17T17:59:50Z","timestamp":1292608790000},"page":"500-512","source":"Crossref","is-referenced-by-count":2,"title":["Polynomial Time Approximation Schemes and Parameterized Complexity"],"prefix":"10.1007","author":[{"given":"Jianer","family":"Chen","sequence":"first","affiliation":[]},{"given":"Xiuzhen","family":"Huang","sequence":"additional","affiliation":[]},{"given":"Iyad A.","family":"Kanj","sequence":"additional","affiliation":[]},{"given":"Ge","family":"Xia","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"38_CR1","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1007\/s00453-001-0116-5","volume":"33","author":"J. Alber","year":"2002","unstructured":"Alber, J., Bodlaender, H., Fernau, H., Kloks, T., Niedermeier, R.: Fixed parameter algorithms for dominating set and related problems on planar graphs. Algorithmica\u00a033, 461\u2013493 (2002)","journal-title":"Algorithmica"},{"key":"38_CR2","volume-title":"Complexity and Approximation, Combinatorial optimization problems and their approximability properties","author":"G. Ausiello","year":"1999","unstructured":"Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti- Spaccamela, A., Protasi, M.: Complexity and Approximation, Combinatorial optimization problems and their approximability properties. Springer, Heidelberg (1999)"},{"key":"38_CR3","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/0304-3975(80)90006-7","volume":"12","author":"G. Ausiello","year":"1980","unstructured":"Ausiello, G., Marchetti-spaccamela, A., Protasi, M.: Toward a unified approach for the classification of NP-complete optimization problems. Theoretical Computer Science\u00a012, 83\u201396 (1980)","journal-title":"Theoretical Computer Science"},{"key":"38_CR4","doi-asserted-by":"publisher","first-page":"753","DOI":"10.1145\/290179.290180","volume":"45","author":"S. Arora","year":"1998","unstructured":"Arora, S.: Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J. ACM\u00a045, 753\u2013782 (1998)","journal-title":"J. ACM"},{"key":"38_CR5","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1145\/174644.174650","volume":"41","author":"B. Baker","year":"1994","unstructured":"Baker, B.: Approximation algorithms for NP-complete problems on planar graphs. J. ACM\u00a041, 153\u2013180 (1994)","journal-title":"J. ACM"},{"key":"38_CR6","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1006\/jcss.1997.1490","volume":"54","author":"L. Cai","year":"1997","unstructured":"Cai, L., Chen, J.: On fixed-parameter tractability and approximability of NP optimization problems. Journal of Computer and System Sciences\u00a054, 465\u2013474 (1997)","journal-title":"Journal of Computer and System Sciences"},{"key":"38_CR7","unstructured":"Cai, L., Fellows, M., Juedes, D., Rosamond, F.: On efficient polynomialtime approximation schemes for problems on planar structures. Journal of Computer and System Sciences (to appear)"},{"key":"38_CR8","doi-asserted-by":"publisher","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. Information Processing Letters\u00a064, 165\u2013171 (1997)","journal-title":"Information Processing Letters"},{"key":"38_CR9","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1016\/0020-0190(91)90003-Z","volume":"39","author":"J. Chen","year":"1991","unstructured":"Chen, J.: Characterizing parallel hierarchies by reducibilities. Information Processing Letters\u00a039, 303\u2013307 (1991)","journal-title":"Information Processing Letters"},{"key":"38_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/S0097539798348110","volume":"31","author":"J. Chen","year":"2001","unstructured":"Chen, J., Miranda, A.: A polynomial time approximation scheme for general multiprocessor job scheduling. SIAM J. on Comp.\u00a031, 1\u201317 (2001)","journal-title":"SIAM J. on Comp."},{"key":"38_CR11","doi-asserted-by":"crossref","unstructured":"Downey, R.: Parameterized complexity for the skeptic. In: Proc. 18th IEEE Annual Conference on Computational Complexity (CCC 2003), pp. 132\u2013153 (2003)","DOI":"10.1109\/CCC.2003.1214417"},{"key":"38_CR12","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R. Downey","year":"1999","unstructured":"Downey, R., Fellows, M.: Parameterized Complexity. Springer, Heidelberg (1999)"},{"key":"38_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1007\/3-540-45678-3_26","volume-title":"Algorithms and Computation","author":"M.R. Fellows","year":"2001","unstructured":"Fellows, M.R.: Parameterized complexity: The main ideas and some research frontiers. In: Eades, P., Takaoka, T. (eds.) ISAAC 2001. LNCS, vol.\u00a02223, pp. 291\u2013307. Springer, Heidelberg (2001)"},{"key":"38_CR14","doi-asserted-by":"publisher","first-page":"1184","DOI":"10.1145\/504794.504798","volume":"48","author":"M. Frick","year":"2001","unstructured":"Frick, M., Grohe, M.: Deciding first-order properties of locally treedecomposable structures. J. ACM\u00a048, 1184\u20131206 (2001)","journal-title":"J. ACM"},{"key":"38_CR15","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M. Garey","year":"1979","unstructured":"Garey, M., Johnson, D.: Computers and Intractability: A Guide to the Theory of NP-Completeness. H. Freeman, New York (1979)"},{"key":"38_CR16","volume-title":"Approximation Algorithms for NP-hard Problems","author":"D. Hochbaum","year":"1997","unstructured":"Hochbaum, D.: Approximation Algorithms for NP-hard Problems. PWS Publishing Company, Boston (1997)"},{"key":"38_CR17","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1145\/321906.321909","volume":"22","author":"O. Ibarra","year":"1975","unstructured":"Ibarra, O., Kim, C.: Fast approximation algorithms for the knapsack and sum of subset problems. J. ACM\u00a022, 463\u2013468 (1975)","journal-title":"J. ACM"},{"key":"38_CR18","doi-asserted-by":"crossref","unstructured":"Khanna, S., Motwani, R.: Towards a syntactic characterization of PTAS. In: Proc. 28th Annual ACM Symp. on Theory of Computing (STOC 1996), pp. 468\u2013477 (1996)","DOI":"10.1145\/237814.237979"},{"key":"38_CR19","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1137\/S0097539795286612","volume":"28","author":"S. Khanna","year":"1998","unstructured":"Khanna, S., Motwani, R., Sudan, M., Vazirani, U.: On syntactic versus computational views of approximability. SIAM J. on Comp.\u00a028, 164\u2013191 (1998)","journal-title":"SIAM J. on Comp."},{"key":"38_CR20","doi-asserted-by":"publisher","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. Theoretical Computer Science\u00a015, 251\u2013277 (1981)","journal-title":"Theoretical Computer Science"},{"key":"38_CR21","doi-asserted-by":"publisher","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. Journal of Computer and System Sciences\u00a043, 425\u2013440 (1991)","journal-title":"Journal of Computer and System Sciences"},{"key":"38_CR22","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1145\/321921.321934","volume":"23","author":"S. Sahni","year":"1976","unstructured":"Sahni, S.: Algorithms for scheduling independent tasks. J. ACM\u00a023, 116\u2013127 (1976)","journal-title":"J. ACM"},{"key":"38_CR23","unstructured":"Woeginger, G.: When does a dynamic programming formulation guarantee the existence of an FPTAS? In: Proc. 10th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA 1999), pp. 820\u2013829 (1999)"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2004"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-28629-5_38.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,3]],"date-time":"2021-05-03T03:27:59Z","timestamp":1620012479000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-28629-5_38"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540228233","9783540286295"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-28629-5_38","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}