{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,1]],"date-time":"2026-02-01T03:54:58Z","timestamp":1769918098868,"version":"3.49.0"},"publisher-location":"Cham","reference-count":44,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319983547","type":"print"},{"value":"9783319983554","type":"electronic"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-98355-4_22","type":"book-chapter","created":{"date-parts":[[2018,8,8]],"date-time":"2018-08-08T10:34:57Z","timestamp":1533724497000},"page":"393-408","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["A Modern View on Stability of Approximation"],"prefix":"10.1007","author":[{"given":"Ralf","family":"Klasing","sequence":"first","affiliation":[]},{"given":"Tobias","family":"M\u00f6mke","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,8,9]]},"reference":[{"issue":"2","key":"22_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 38(2), 59\u201367 (2001)","journal-title":"Networks"},{"issue":"1","key":"22_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 parametrized triangle inequalities. SIAM J. Discret. Math. 8(1), 1\u201316 (1995)","journal-title":"SIAM J. Discret. Math."},{"issue":"5","key":"22_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. J. ACM 45(5), 753\u2013782 (1998)","journal-title":"J. ACM"},{"issue":"1\u20132","key":"22_CR4","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1007\/s10107-003-0438-y","volume":"97","author":"S Arora","year":"2003","unstructured":"Arora, S.: Approximation schemes for NP-hard geometric optimization problems: a survey. Math. Progr. 97(1\u20132), 43\u201369 (2003)","journal-title":"Math. Progr."},{"key":"22_CR5","doi-asserted-by":"crossref","unstructured":"Arora, S., Raghavan, P., Rao, S.: Approximation schemes for Euclidean $$k$$-medians and related problems. In: Proceedings of 30th Annual ACM Symposium on the Theory of Computing (STOC 1998), pp. 106\u2013113 (1998)","DOI":"10.1145\/276698.276718"},{"issue":"4","key":"22_CR6","doi-asserted-by":"publisher","first-page":"1563","DOI":"10.1137\/130913328","volume":"45","author":"Y Bartal","year":"2016","unstructured":"Bartal, Y., Gottlieb, L.-A., Krauthgamer, R.: The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme. SIAM J. Comput. 45(4), 1563\u20131581 (2016)","journal-title":"SIAM J. Comput."},{"issue":"1\u20132","key":"22_CR7","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/S0020-0190(99)00160-X","volume":"73","author":"MA Bender","year":"2000","unstructured":"Bender, M.A., Chekuri, C.: Performance guarantees for the TSP with a parameterized triangle inequality. Inf. Process. Lett. 73(1\u20132), 17\u201321 (2000)","journal-title":"Inf. Process. Lett."},{"issue":"1\u20133","key":"22_CR8","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1016\/j.tcs.2004.06.019","volume":"326","author":"H-J B\u00f6ckenhauer","year":"2004","unstructured":"B\u00f6ckenhauer, H.-J., Bongartz, D., Hromkovi\u010d, J., Klasing, R., Proietti, G., Seibert, S., Unger, W.: On the hardness of constructing minimal 2-connected spanning subgraphs in complete graphs with sharpened triangle inequality. Theor. Comput. Sci. 326(1\u20133), 137\u2013153 (2004)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"22_CR9","doi-asserted-by":"publisher","first-page":"605","DOI":"10.1016\/j.jda.2008.03.003","volume":"6","author":"H-J B\u00f6ckenhauer","year":"2008","unstructured":"B\u00f6ckenhauer, H.-J., et al.: On $$k$$-connectivity problems with sharpened triangle inequality. J. Discret. Algorithms 6(4), 605\u2013617 (2008)","journal-title":"J. Discret. Algorithms"},{"issue":"3","key":"22_CR10","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/S0020-0190(00)00089-2","volume":"75","author":"H-J B\u00f6ckenhauer","year":"2000","unstructured":"B\u00f6ckenhauer, H.-J., Hromkovi\u010d, J., Klasing, R., Seibert, S., Unger, W.: Approximation algorithms for the TSP with sharpened triangle inequality. Inf. Process. Lett. 75(3), 133\u2013138 (2000)","journal-title":"Inf. Process. Lett."},{"key":"22_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1007\/3-540-46541-3_32","volume-title":"STACS 2000","author":"H-J B\u00f6ckenhauer","year":"2000","unstructured":"B\u00f6ckenhauer, H.-J., Hromkovi\u010d, J., Klasing, R., Seibert, S., Unger, W.: An improved lower bound on the approximability of metric TSP and approximation algorithms for the TSP with sharpened triangle inequality. In: Reichel, H., Tison, S. (eds.) STACS 2000. LNCS, vol. 1770, pp. 382\u2013394. Springer, Heidelberg (2000). https:\/\/doi.org\/10.1007\/3-540-46541-3_32"},{"issue":"1","key":"22_CR12","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/S0304-3975(01)00287-0","volume":"285","author":"H-J B\u00f6ckenhauer","year":"2002","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. Theor. Comput. Sci. 285(1), 3\u201324 (2002)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"22_CR13","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1051\/ita:2000115","volume":"34","author":"H-J B\u00f6ckenhauer","year":"2000","unstructured":"B\u00f6ckenhauer, H.-J., Seibert, S.: Improved lower bounds on the approximability of the traveling salesman problem. RAIRO - Theor. Inf. Appl. 34(3), 213\u2013255 (2000)","journal-title":"RAIRO - Theor. Inf. Appl."},{"key":"22_CR14","doi-asserted-by":"crossref","unstructured":"B\u00f6ckenhauer, H.-J., Seibert, S., Hromkovi\u010d, J.: Stability of approximation. In: Handbook of Approximation Algorithms and Metaheuristics. Chapman and Hall\/CRC (2007)","DOI":"10.1201\/9781420010749.ch31"},{"issue":"6","key":"22_CR15","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"HL Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25(6), 1305\u20131317 (1996)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"22_CR16","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1006\/jagm.1995.1009","volume":"18","author":"HL Bodlaender","year":"1995","unstructured":"Bodlaender, H.L., Gilbert, J.R., Hafsteinsson, H., Kloks, T.: Approximating treewidth, pathwidth, frontsize, and shortest elimination tree. J. Algorithms 18(2), 238\u2013255 (1995)","journal-title":"J. Algorithms"},{"issue":"2","key":"22_CR17","doi-asserted-by":"publisher","first-page":"358","DOI":"10.1006\/jagm.1996.0049","volume":"21","author":"HL Bodlaender","year":"1996","unstructured":"Bodlaender, H.L., Kloks, T.: Efficient and constructive algorithms for the pathwidth and treewidth of graphs. J. Algorithms 21(2), 358\u2013402 (1996)","journal-title":"J. Algorithms"},{"issue":"3","key":"22_CR18","first-page":"19:1","volume":"11","author":"G Borradaile","year":"2015","unstructured":"Borradaile, G., Klein, P.N., Mathieu, C.: A polynomial-time approximation scheme for Euclidean Steiner forest. ACM Trans. Algorithms 11(3), 19:1\u201319:20 (2015)","journal-title":"ACM Trans. Algorithms"},{"key":"22_CR19","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1016\/j.jcss.2017.09.012","volume":"92","author":"L-H Chen","year":"2018","unstructured":"Chen, L.-H., et al.: Approximability and inapproximability of the star $$p$$-hub center problem with parameterized triangle inequality. J. Comput. Syst. Sci. 92, 92\u2013112 (2018)","journal-title":"J. Comput. Syst. Sci."},{"key":"22_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"112","DOI":"10.1007\/978-3-319-62389-4_10","volume-title":"Computing and Combinatorics","author":"L-H Chen","year":"2017","unstructured":"Chen, L.-H., Hsieh, S.-Y., Hung, L.-J., Klasing, R.: The approximability of the p-hub center problem with parameterized triangle inequality. In: Cao, Y., Chen, J. (eds.) COCOON 2017. LNCS, vol. 10392, pp. 112\u2013123. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-62389-4_10"},{"key":"22_CR21","unstructured":"Christofides, N.: Worst-case analysis of a new heuristic for the travelling salesman problem. Technical report 388, Graduate School of Industrial Administration, Carnegie-Mellon University (1976)"},{"issue":"1","key":"22_CR22","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1007\/PL00009449","volume":"22","author":"KL Clarkson","year":"1999","unstructured":"Clarkson, K.L.: Nearest neighbor queries in metric spaces. Discret. Comput. Geom. 22(1), 63\u201393 (1999)","journal-title":"Discret. Comput. Geom."},{"key":"22_CR23","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2009","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. The MIT Press, Cambridge (2009)","edition":"3"},{"issue":"3","key":"22_CR24","doi-asserted-by":"publisher","first-page":"1514","DOI":"10.1137\/100800452","volume":"27","author":"G Ding","year":"2013","unstructured":"Ding, G., Dziobiak, S.: On 3-connected graphs of path-width at most three. SIAM J. Discret. Math. 27(3), 1514\u20131526 (2013)","journal-title":"SIAM J. Discret. Math."},{"key":"22_CR25","series-title":"Texts in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, London (2013). https:\/\/doi.org\/10.1007\/978-1-4471-5559-1"},{"key":"22_CR26","doi-asserted-by":"crossref","unstructured":"Garg, N., Kumar, A.: Minimizing average flow-time: upper and lower bounds. In: Proceedings of 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), pp. 603\u2013613. IEEE Computer Society (2007)","DOI":"10.1109\/FOCS.2007.52"},{"key":"22_CR27","series-title":"Algorithms and Combinatorics","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-78240-4","volume-title":"Geometric Algorithms and Combinatorial Optimization","author":"M Gr\u00f6tschel","year":"1988","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Algorithms and Combinatorics, vol. 2. Springer, Heidelberg (1988). https:\/\/doi.org\/10.1007\/978-3-642-78240-4"},{"key":"22_CR28","doi-asserted-by":"crossref","unstructured":"Gupta, A. Krauthgamer, R., Lee, J.R.: Bounded geometries, fractals, and low-distortion embeddings. In: Proceedings of 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2003), pp. 534\u2013543. IEEE Computer Society (2003)","DOI":"10.1109\/SFCS.2003.1238226"},{"issue":"1","key":"22_CR29","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/BF02523693","volume":"18","author":"MM Halld\u00f3rsson","year":"1997","unstructured":"Halld\u00f3rsson, M.M., Radhakrishnan, J.: Greed is good: approximating independent sets in sparse and bounded-degree graphs. Algorithmica 18(1), 145\u2013163 (1997)","journal-title":"Algorithmica"},{"key":"22_CR30","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1007\/978-3-642-60207-8_21","volume-title":"Jewels are Forever","author":"J Hromkovi\u0109","year":"1999","unstructured":"Hromkovi\u0109, J.: Stability of approximation algorithms and the knapsack problem. In: Karhum\u00e4ki, J., Maurer, H., Paun, G., Rozenberg, G. (eds.) Jewels are Forever, pp. 238\u2013249. Springer, Heidelberg (1999). https:\/\/doi.org\/10.1007\/978-3-642-60207-8_21"},{"key":"22_CR31","series-title":"Texts in Theoretical Computer Science. An EATCS Series","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-05269-3","volume-title":"Algorithmics for Hard Problems - Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics","author":"J Hromkovi\u010d","year":"2004","unstructured":"Hromkovi\u010d, J.: Algorithmics for Hard Problems - Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics. Texts in Theoretical Computer Science. An EATCS Series. Springer, Heidelberg (2004). https:\/\/doi.org\/10.1007\/978-3-662-05269-3"},{"key":"22_CR32","series-title":"IFIP International Federation for Information Processing","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/1-4020-8141-3_2","volume-title":"Exploring New Frontiers of Theoretical Informatics","author":"J Hromkovi\u010d","year":"2004","unstructured":"Hromkovi\u010d, J.: Stability of approximation in discrete optimization. In: Levy, J.-J., Mayr, E.W., Mitchell, J.C. (eds.) TCS 2004. IIFIP, vol. 155, pp. 3\u201318. Springer, Boston, MA (2004). https:\/\/doi.org\/10.1007\/1-4020-8141-3_2"},{"key":"22_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/978-3-642-13182-0_17","volume-title":"Computer Science \u2013 Theory and Applications","author":"J Hromkovi\u010d","year":"2010","unstructured":"Hromkovi\u010d, J.: Algorithmics \u2013 is there hope for a unified theory? In: Ablayev, F., Mayr, E.W. (eds.) CSR 2010. LNCS, vol. 6072, pp. 181\u2013194. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-13182-0_17"},{"key":"22_CR34","first-page":"143","volume":"33","author":"HA Kierstead","year":"1981","unstructured":"Kierstead, H.A., Trotter, W.T.: An extremal problem in recursive combinatorics. Congr. Numer. 33, 143\u2013153 (1981)","journal-title":"Congr. Numer."},{"issue":"3","key":"22_CR35","doi-asserted-by":"publisher","first-page":"757","DOI":"10.1137\/S0097539702404055","volume":"37","author":"SG Kolliopoulos","year":"2007","unstructured":"Kolliopoulos, S.G., Rao, S.: A nearly linear-time approximation scheme for the Euclidean $$k$$-median problem. SIAM J. Comput. 37(3), 757\u2013782 (2007)","journal-title":"SIAM J. Comput."},{"key":"22_CR36","doi-asserted-by":"crossref","unstructured":"Kozma, L., M\u00f6mke, T.: Maximum scatter TSP in doubling metrics. In: Proceedings of 28th ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), pp. 143\u2013153 (2017)","DOI":"10.1137\/1.9781611974782.10"},{"key":"22_CR37","doi-asserted-by":"crossref","unstructured":"Leonardi, S., Raz, D.: Approximating total flow time on parallel machines. In: Proceedings of 29th Annual ACM Symposium on the Theory of Computing (STOC 1997), pp. 110\u2013119. ACM (1997)","DOI":"10.1145\/258533.258562"},{"issue":"6","key":"22_CR38","doi-asserted-by":"publisher","first-page":"875","DOI":"10.1016\/j.jcss.2006.10.018","volume":"73","author":"S Leonardi","year":"2007","unstructured":"Leonardi, S., Raz, D.: Approximating total flow time on parallel machines. J. Comput. Syst. Sci. 73(6), 875\u2013891 (2007)","journal-title":"J. Comput. Syst. Sci."},{"issue":"11","key":"22_CR39","doi-asserted-by":"publisher","first-page":"866","DOI":"10.1016\/j.ipl.2015.06.003","volume":"115","author":"T M\u00f6mke","year":"2015","unstructured":"M\u00f6mke, T.: An improved approximation algorithm for the traveling salesman problem with relaxed triangle inequality. Inf. Process. Lett. 115(11), 866\u2013871 (2015)","journal-title":"Inf. Process. Lett."},{"key":"22_CR40","doi-asserted-by":"crossref","unstructured":"Nayyar, K., Raghvendra, S.: An input sensitive online algorithm for the metric bipartite matching problem. In: Proceedings of 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS 2017), pp. 505\u2013515. IEEE Computer Society (2017)","DOI":"10.1109\/FOCS.2017.53"},{"key":"22_CR41","unstructured":"Raghvendra, S.: A robust and optimal online algorithm for minimum metric bipartite matching. In: APPROX-RANDOM. LIPIcs, vol. 60, pp. 18:1\u201318:16. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2016)"},{"key":"22_CR42","doi-asserted-by":"crossref","unstructured":"Talwar, K.: Bypassing the embedding: algorithms for low dimensional metrics. In: Proceedings of 36th Annual ACM Symposium on Theory of Computing (STOC 2004), pp. 281\u2013290 (2004)","DOI":"10.1145\/1007352.1007399"},{"issue":"2","key":"22_CR43","doi-asserted-by":"publisher","first-page":"475","DOI":"10.1137\/S0097539799352735","volume":"30","author":"L Trevisan","year":"2000","unstructured":"Trevisan, L.: When Hamming meets Euclid: the approximability of geometric TSP and Steiner tree. SIAM J. Comput. 30(2), 475\u2013485 (2000)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"22_CR44","doi-asserted-by":"publisher","first-page":"103","DOI":"10.4086\/toc.2007.v003a006","volume":"3","author":"D Zuckerman","year":"2007","unstructured":"Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. Theory Comput. 3(1), 103\u2013128 (2007)","journal-title":"Theory Comput."}],"container-title":["Lecture Notes in Computer Science","Adventures Between Lower Bounds and Higher Altitudes"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-98355-4_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,6]],"date-time":"2025-07-06T07:38:21Z","timestamp":1751787501000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-98355-4_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319983547","9783319983554"],"references-count":44,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-98355-4_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"9 August 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}