{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T00:24:41Z","timestamp":1725582281417},"publisher-location":"Berlin, Heidelberg","reference-count":46,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642193903"},{"type":"electronic","value":"9783642193910"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-19391-0_1","type":"book-chapter","created":{"date-parts":[[2011,4,28]],"date-time":"2011-04-28T08:53:35Z","timestamp":1303980815000},"page":"3-19","source":"Crossref","is-referenced-by-count":0,"title":["Improved Approximations for Hard Optimization Problems via Problem Instance Classification"],"prefix":"10.1007","author":[{"given":"Hans-Joachim","family":"B\u00f6ckenhauer","sequence":"first","affiliation":[]},{"given":"Juraj","family":"Hromkovi\u010d","sequence":"additional","affiliation":[]},{"given":"Tobias","family":"M\u00f6mke","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"2","key":"1_CR1","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1002\/net.1024","volume":"38","author":"T. Andreae","year":"2001","unstructured":"Andreae, T.: On the traveling salesman problem restricted to inputs satisfying a relaxed triangle inequality. Networks\u00a038(2), 59\u201367 (2001)","journal-title":"Networks"},{"key":"1_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/S0895480192240226","volume":"8","author":"T. Andreae","year":"1995","unstructured":"Andreae, T., Bandelt, H.J.: Performance guarantees for approximation algorithms depending on parameterized triangle inequalities. SIAM Journal on Discrete Mathematics\u00a08, 1\u201316 (1995)","journal-title":"SIAM Journal on Discrete Mathematics"},{"issue":"5","key":"1_CR3","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. Journal of the ACM\u00a045(5), 753\u2013782 (1998)","journal-title":"Journal of the ACM"},{"key":"1_CR4","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-58412-1","volume-title":"Complexity and Approximation","author":"G. Ausiello","year":"1999","unstructured":"Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.: Complexity and Approximation. Springer, Berlin (1999)"},{"key":"1_CR5","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/S0020-0190(99)00160-X","volume":"73","author":"M. Bender","year":"2000","unstructured":"Bender, M., Chekuri, C.: Performance guarantees for TSP with a parametrized triangle inequality. Information Processing Letters\u00a073, 17\u201321 (2000)","journal-title":"Information Processing Letters"},{"issue":"4","key":"1_CR6","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/0020-0190(89)90039-2","volume":"32","author":"M.W. Bern","year":"1989","unstructured":"Bern, M.W., Plassmann, P.E.: The Steiner problem with edge lengths 1 and 2. Information Processing Letters\u00a032(4), 171\u2013176 (1989)","journal-title":"Information Processing Letters"},{"key":"1_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1007\/3-540-46521-9_7","volume-title":"Algorithms and Complexity","author":"H.-J. B\u00f6ckenhauer","year":"2000","unstructured":"B\u00f6ckenhauer, H.-J., Hromkovi\u010d, J., Klasing, R., Seibert, S., Unger, W.: Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem. In: Bongiovanni, G., Petreschi, R., Gambosi, G. (eds.) CIAC 2000. LNCS, vol.\u00a01767, pp. 72\u201386. Springer, Heidelberg (2000)"},{"issue":"3","key":"1_CR8","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1007\/s00224-007-1347-x","volume":"41","author":"H.-J. B\u00f6ckenhauer","year":"2007","unstructured":"B\u00f6ckenhauer, H.-J., Hromkovi\u010d, J., Kneis, J., Kupke, J.: The parameterized approximability of TSP with deadlines. Theory of Computing Systems\u00a041(3), 431\u2013444 (2007)","journal-title":"Theory of Computing Systems"},{"issue":"36","key":"1_CR9","doi-asserted-by":"publisher","first-page":"3428","DOI":"10.1016\/j.tcs.2008.04.039","volume":"410","author":"H.-J. B\u00f6ckenhauer","year":"2009","unstructured":"B\u00f6ckenhauer, H.-J., Hromkovi\u010d, J., Kr\u00e1lovi\u010d, R., M\u00f6mke, T., Rossmanith, P.: Reoptimization of Steiner trees: Changing the terminal set. Theoretical Computer Science\u00a0410(36), 3428\u20133435 (2009)","journal-title":"Theoretical Computer Science"},{"key":"1_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1007\/978-3-540-77566-9_5","volume-title":"SOFSEM 2008: Theory and Practice of Computer Science","author":"H.-J. B\u00f6ckenhauer","year":"2008","unstructured":"B\u00f6ckenhauer, H.-J., Hromkovi\u010d, J., M\u00f6mke, T., Widmayer, P.: On the hardness of reoptimization. In: Geffert, V., Karhum\u00e4ki, J., Bertoni, A., Preneel, B., N\u00e1vrat, P., Bielikov\u00e1, M. (eds.) SOFSEM 2008. LNCS, vol.\u00a04910, pp. 50\u201365. Springer, Heidelberg (2008)"},{"doi-asserted-by":"crossref","unstructured":"B\u00f6ckenhauer, H.-J., Hromkovi\u010d, J., Seibert, S.: Stability of approximation. In: Gonzalez, T.F. (ed.) Handbook of Approximation Algorithms and Metaheuristics, ch. 31. Chapman & Hall\/CRC (2007)","key":"1_CR11","DOI":"10.1201\/9781420010749.ch31"},{"key":"1_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/978-3-642-13073-1_7","volume-title":"Algorithms and Complexity","author":"H.-J. B\u00f6ckenhauer","year":"2010","unstructured":"B\u00f6ckenhauer, H.-J., Klasing, R., M\u00f6mke, T., Steinov\u00e1, M.: Improved approximations for TSP with simple precedence constraints. In: Calamoneri, T., Diaz, J. (eds.) CIAC 2010. LNCS, vol.\u00a06078, pp. 61\u201372. Springer, Heidelberg (2010)"},{"key":"1_CR13","series-title":"Lecture Notes in Computer Science","volume-title":"Parameterized and Exact Computation","year":"2006","unstructured":"Bodlaender, H.L., Langston, M.A. (eds.): IWPEC 2006. LNCS, vol.\u00a04169. Springer, Heidelberg (2006)"},{"unstructured":"Cabello, S., Eppstein, D., Klav\u017ear, S.: The Fibonacci dimension of a graph. CoRR abs\/0903.2507 (2009)","key":"1_CR14"},{"issue":"2","key":"1_CR15","doi-asserted-by":"publisher","first-page":"398","DOI":"10.1007\/s00453-008-9223-x","volume":"57","author":"L. Cai","year":"2010","unstructured":"Cai, L., Huang, X.: Fixed-parameter approximation: Conceptual framework and approximability results. Algorithmica\u00a057(2), 398\u2013412 (2010)","journal-title":"Algorithmica"},{"issue":"4","key":"1_CR16","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(4), 165\u2013171 (1997)","journal-title":"Information Processing Letters"},{"key":"1_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/11847250_10","volume-title":"Parameterized and Exact Computation","author":"Y. Chen","year":"2006","unstructured":"Chen, Y., Grohe, M., Gr\u00fcber, M.: On parameterized approximability. In: Bodlaender, H.L., Langston, M.A. (eds.) IWPEC 2006. LNCS, vol.\u00a04169, pp. 109\u2013120. Springer, Heidelberg (2006)"},{"unstructured":"Christofides, N.: Worst-case analysis of a new heuristic for the travelling salesman problem. Tech. Rep. 388, Graduate School of Industrial Administration, Carnegie-Mellon University (1976)","key":"1_CR18"},{"key":"1_CR19","first-page":"590","volume-title":"Proc. of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005)","author":"E.D. Demaine","year":"2005","unstructured":"Demaine, E.D., Hajiaghayi, M.T.: Bidimensionality: New connections between FPT algorithms and PTASs. In: Proc. of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), pp. 590\u2013601. SIAM, Philadelphia (2005)"},{"issue":"3","key":"1_CR20","doi-asserted-by":"publisher","first-page":"292","DOI":"10.1093\/comjnl\/bxm033","volume":"51","author":"E.D. Demaine","year":"2008","unstructured":"Demaine, E.D., Hajiaghayi, M.: The bidimensionality theory and its algorithmic applications. Computer Journal\u00a051(3), 292\u2013302 (2008)","journal-title":"Computer Journal"},{"issue":"4","key":"1_CR21","doi-asserted-by":"publisher","first-page":"873","DOI":"10.1137\/S0097539792228228","volume":"24","author":"R.G. Downey","year":"1995","unstructured":"Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness i: Basic results. SIAM Journal on Computing\u00a024(4), 873\u2013921 (1995)","journal-title":"SIAM Journal on Computing"},{"key":"1_CR22","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/0304-3975(94)00097-3","volume":"141","author":"R.G. Downey","year":"1995","unstructured":"Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness ii: On completeness for W[1]. Theoretical Computer Science\u00a0141, 109\u2013131 (1995)","journal-title":"Theoretical Computer Science"},{"key":"1_CR23","series-title":"Monographs in Computer Science","doi-asserted-by":"publisher","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. Monographs in Computer Science. Springer, New York (1999)"},{"key":"1_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/11847250_11","volume-title":"Parameterized and Exact Computation","author":"R.G. Downey","year":"2006","unstructured":"Downey, R.G., Fellows, M.R., McCartin, C.: Parameterized approximation problems. In: Bodlaender, H.L., Langston, M.A. (eds.) IWPEC 2006. LNCS, vol.\u00a04169, pp. 121\u2013129. Springer, Heidelberg (2006)"},{"issue":"1","key":"1_CR25","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1016\/j.ipl.2008.09.017","volume":"109","author":"R.G. Downey","year":"2008","unstructured":"Downey, R.G., Fellows, M.R., McCartin, C., Rosamond, F.A.: Parameterized approximation of dominating set problems. Information Processing Letters\u00a0109(1), 68\u201370 (2008)","journal-title":"Information Processing Letters"},{"key":"1_CR26","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1002\/net.3230010302","volume":"1","author":"S.E. Dreyfus","year":"1971","unstructured":"Dreyfus, S.E., Wagner, R.A.: The Steiner problem in graphs. Networks\u00a01, 195\u2013207 (1971\/1972)","journal-title":"Networks"},{"key":"1_CR27","doi-asserted-by":"publisher","first-page":"1076","DOI":"10.1137\/1.9781611973075.87","volume-title":"Proc. of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010)","author":"D. Eppstein","year":"2010","unstructured":"Eppstein, D.: Paired approximation problems and incompatible inapproximabilities. In: Charikar, M. (ed.) Proc. of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010), pp. 1076\u20131086. SIAM, Philadelphia (2010)"},{"key":"1_CR28","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Heidelberg (2006)"},{"issue":"6","key":"1_CR29","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"M.X. Goemans","year":"1995","unstructured":"Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM\u00a042(6), 1115\u20131145 (1995)","journal-title":"Journal of the ACM"},{"issue":"3","key":"1_CR30","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1007\/s00224-007-1309-3","volume":"41","author":"J. Guo","year":"2007","unstructured":"Guo, J., Niedermeier, R., Wernicke, S.: Parameterized complexity of vertex cover variants. Theory of Computing Systems\u00a041(3), 501\u2013520 (2007)","journal-title":"Theory of Computing Systems"},{"key":"1_CR31","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1090\/S0002-9947-1965-0170805-7","volume":"117","author":"J. Hartmanis","year":"1965","unstructured":"Hartmanis, J., Stearns, R.E.: On the computational complexity of algorithms. Transactions of the American Mathematical Society\u00a0117, 285\u2013306 (1965)","journal-title":"Transactions of the American Mathematical Society"},{"issue":"5","key":"1_CR32","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1016\/0167-6377(91)90016-I","volume":"10","author":"J.A. Hoogeveen","year":"1991","unstructured":"Hoogeveen, J.A.: Analysis of Christofides\u2019 heuristic: some paths are more difficult than cycles. Operations Research Letters\u00a010(5), 291\u2013295 (1991)","journal-title":"Operations Research Letters"},{"unstructured":"Hromkovi\u010d, J.: Algorithmics for Hard Problems. In: Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics. Springer, Berlin (2003)","key":"1_CR33"},{"issue":"2","key":"1_CR34","doi-asserted-by":"publisher","first-page":"457","DOI":"10.1137\/090749451","volume":"24","author":"K. Jansen","year":"2010","unstructured":"Jansen, K.: An EPTAS for scheduling jobs on uniform processors: Using an MILP relaxation with a constant number of integral variables. SIAM Journal on Discrete Mathematics\u00a024(2), 457\u2013485 (2010)","journal-title":"SIAM Journal on Discrete Mathematics"},{"issue":"1","key":"1_CR35","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1093\/comjnl\/bxm048","volume":"51","author":"D. Marx","year":"2008","unstructured":"Marx, D.: Parameterized complexity and approximation algorithms. The Computer Journal\u00a051(1), 60\u201378 (2008)","journal-title":"The Computer Journal"},{"key":"1_CR36","series-title":"Oxford Lecture Series in Mathematics and Its Applications","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed Parameter Algorithms","author":"R. Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed Parameter Algorithms. Oxford Lecture Series in Mathematics and Its Applications. Oxford University Press, USA (2006)"},{"key":"1_CR37","volume-title":"Combinatorial Optimization: Algorithms and Complexity","author":"C.H. Papadimitriou","year":"1982","unstructured":"Papadimitriou, C.H., Steiglitz, K.: Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, Englewood Cliffs (1982)"},{"key":"1_CR38","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/BF01202286","volume":"4","author":"E. Petrank","year":"1994","unstructured":"Petrank, E.: The hardness of approximation: gap location. Computational Complexity\u00a04, 133\u2013157 (1994)","journal-title":"Computational Complexity"},{"key":"1_CR39","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"474","DOI":"10.1007\/978-3-540-45078-8_41","volume-title":"Algorithms and Data Structures","author":"E. Prieto","year":"2003","unstructured":"Prieto, E., Sloper, C.: Either\/or: using vertex cover structure in designing FPT-algorithms\u2014the case of k-Internal Spanning Tree. In: Dehne, F.K.H.A., Sack, J.R., Smid, M.H.M. (eds.) WADS 2003. LNCS, vol.\u00a02748, pp. 474\u2013483. Springer, Heidelberg (2003)"},{"key":"1_CR40","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/S0065-2458(08)60520-3","volume":"15","author":"J.R. Rice","year":"1976","unstructured":"Rice, J.R.: The algorithm selection problem. Advances in Computers\u00a015, 65\u2013118 (1976)","journal-title":"Advances in Computers"},{"issue":"3","key":"1_CR41","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1145\/321958.321975","volume":"23","author":"S. Sahni","year":"1976","unstructured":"Sahni, S., Gonzalez, T.F.: P-complete approximation problems. Journal of the ACM\u00a023(3), 555\u2013565 (1976)","journal-title":"Journal of the ACM"},{"key":"1_CR42","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"382","DOI":"10.1007\/978-3-540-45198-3_32","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"A.D. Scott","year":"2003","unstructured":"Scott, A.D., Sorkin, G.B.: Faster algorithms for MAX CUT and MAX CSP, with polynomial expected time for sparse instances. In: Arora, S., Jansen, K., Rolim, J.D.P., Sahai, A. (eds.) RANDOM 2003 and APPROX 2003. LNCS, vol.\u00a02764, pp. 382\u2013395. Springer, Heidelberg (2003)"},{"key":"1_CR43","first-page":"179","volume-title":"Proc.\u00a0of the 6th Annual Symposium on Switching and Automata Theory","author":"R.E. Stearns","year":"1965","unstructured":"Stearns, R.E., Hartmanis, J., Lewis II, P.M.: Hierarchies of memory limited computations. In: Proc.\u00a0of the 6th Annual Symposium on Switching and Automata Theory, pp. 179\u2013190. IEEE, Los Alamitos (1965)"},{"issue":"42","key":"1_CR44","first-page":"230","volume":"2","author":"A.M. Turing","year":"1936","unstructured":"Turing, A.M.: On computable numbers, with an application to the entscheidungsproblem. Proceedings of the London Mathematical Society\u00a02(42), 230\u2013265 (1936)","journal-title":"Proceedings of the London Mathematical Society"},{"key":"1_CR45","first-page":"1","volume-title":"Proc.\u00a0of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u00a02006)","author":"V. Vassilevska","year":"2006","unstructured":"Vassilevska, V., Williams, R., Woo, S.L.M.: Confronting hardness using a hybrid approach. In: Proc.\u00a0of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u00a02006), pp. 1\u201310. SIAM, New York (2006)"},{"key":"1_CR46","volume-title":"Approximation Algorithms","author":"V.V. Vazirani","year":"2004","unstructured":"Vazirani, V.V.: Approximation Algorithms. Springer, Heidelberg (2004)"}],"container-title":["Lecture Notes in Computer Science","Rainbow of Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-19391-0_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,23]],"date-time":"2019-05-23T05:42:46Z","timestamp":1558590166000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-19391-0_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642193903","9783642193910"],"references-count":46,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-19391-0_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}