{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T04:38:08Z","timestamp":1777351088678,"version":"3.51.4"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2020,9,22]],"date-time":"2020-09-22T00:00:00Z","timestamp":1600732800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,9,22]],"date-time":"2020-09-22T00:00:00Z","timestamp":1600732800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["TH 1852\/4-1"],"award-info":[{"award-number":["TH 1852\/4-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["RU 1524\/6-1"],"award-info":[{"award-number":["RU 1524\/6-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001655","name":"Deutscher Akademischer Austauschdienst","doi-asserted-by":"publisher","award":["57388848"],"award-info":[{"award-number":["57388848"]}],"id":[{"id":"10.13039\/501100001655","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100006537","name":"Campus France","doi-asserted-by":"publisher","award":["40407WF"],"award-info":[{"award-number":["40407WF"]}],"id":[{"id":"10.13039\/501100006537","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2022,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In a (linear) parametric optimization problem, the objective value of each feasible solution is an affine function of a real-valued parameter and one is interested in computing a solution for each possible value of the parameter. For many important parametric optimization problems including the parametric versions of the shortest path problem, the assignment problem, and the minimum cost flow problem, however, the piecewise linear function mapping the parameter to the optimal objective value of the corresponding non-parametric instance (the <jats:italic>optimal value function<\/jats:italic>) can have super-polynomially many breakpoints (points of slope change). This implies that any optimal algorithm for such a problem must output a super-polynomial number of solutions. We provide a method for lifting approximation algorithms for non-parametric optimization problems to their parametric counterparts that is applicable to a general class of parametric optimization problems. The approximation guarantee achieved by this method for a parametric problem is arbitrarily close to the approximation guarantee of the algorithm for the corresponding non-parametric problem. It outputs polynomially many solutions and has polynomial running time if the non-parametric algorithm has polynomial running time. In the case that the non-parametric problem can be solved exactly in polynomial time or that an FPTAS is available, the method yields an FPTAS. In particular, under mild assumptions, we obtain the first parametric FPTAS for each of the specific problems mentioned above and a <jats:inline-formula><jats:alternatives><jats:tex-math>$$(3\/2 + \\varepsilon )$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mn>3<\/mml:mn>\n                    <mml:mo>\/<\/mml:mo>\n                    <mml:mn>2<\/mml:mn>\n                    <mml:mo>+<\/mml:mo>\n                    <mml:mi>\u03b5<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-approximation algorithm for the parametric metric traveling salesman problem. Moreover, we describe a post-processing procedure that, if the non-parametric problem can be solved exactly in polynomial time, further decreases the number of returned solutions such that the method outputs at most twice as many solutions as needed at minimum for achieving the desired approximation guarantee.<\/jats:p>","DOI":"10.1007\/s10878-020-00646-5","type":"journal-article","created":{"date-parts":[[2020,9,22]],"date-time":"2020-09-22T20:57:14Z","timestamp":1600808234000},"page":"1328-1358","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["An approximation algorithm for a general class of parametric optimization problems"],"prefix":"10.1007","volume":"43","author":[{"given":"Cristina","family":"Bazgan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6230-1253","authenticated-orcid":false,"given":"Arne","family":"Herzel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefan","family":"Ruzika","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Clemens","family":"Thielen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Vanderpooten","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,9,22]]},"reference":[{"key":"646_CR1","volume-title":"Network flows","author":"RK Ahuja","year":"1993","unstructured":"Ahuja RK, Magnanti TL, Orlin JB (1993) Network flows. Prentice Hall, Englewood Cliffs"},{"issue":"1","key":"646_CR2","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/0166-218X(93)90245-J","volume":"41","author":"T Arai","year":"1993","unstructured":"Arai T, Ueno S, Kajitani Y (1993) Generalization of a theorem on the parametric maximum flow problem. Discrete Appl Math 41(1):69\u201374","journal-title":"Discrete Appl Math"},{"key":"646_CR3","doi-asserted-by":"crossref","unstructured":"Bazgan C, Herzel A, Ruzika S, Thielen C, Vanderpooten D (2019) An FPTAS for a general class of parametric optimization problems. In: Proceedings of the 25th international computing and combinatorics conference (COCOON), LNCS, vol 11653, pp 25\u201337","DOI":"10.1007\/978-3-030-26176-4_3"},{"issue":"1","key":"646_CR4","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1007\/BF02591893","volume":"26","author":"PJ Carstensen","year":"1983","unstructured":"Carstensen PJ (1983a) Complexity of some parametric integer and network programming problems. Math Program 26(1):64\u201375","journal-title":"Math Program"},{"key":"646_CR5","unstructured":"Carstensen PJ (1983b) The complexity of some problems in parametric, linear, and combinatorial programming. Ph.D. thesis, University of Michigan"},{"key":"646_CR6","unstructured":"Christofides N (1976) Worst-case analysis of a new heuristic for the travelling salesman problem. Technical Report 388, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh"},{"issue":"3","key":"646_CR7","doi-asserted-by":"publisher","first-page":"811","DOI":"10.1137\/13093875X","volume":"45","author":"C Daskalakis","year":"2016","unstructured":"Daskalakis C, Diakonikolas I, Yannakakis M (2016) How good is the chord algorithm? SIAM J Comput 45(3):811\u2013858","journal-title":"SIAM J Comput"},{"key":"646_CR8","unstructured":"Diakonikolas I (2011) Approximation of multiobjective optimization problems. Ph.D. thesis, Columbia University"},{"key":"646_CR9","unstructured":"Diakonikolas I, Yannakakis M (2008) Succinct approximate convex Pareto curves. In: Proceedings of the 19th annual ACM-SIAM symposium on discrete algorithms (SODA), pp 74\u201383. SIAM"},{"issue":"4","key":"646_CR10","doi-asserted-by":"publisher","first-page":"619","DOI":"10.1145\/321978.321982","volume":"23","author":"MJ Eisner","year":"1976","unstructured":"Eisner MJ, Severance DG (1976) Mathematical techniques for efficient record segmentation in large shared databases. J ACM 23(4):619\u2013635","journal-title":"J ACM"},{"key":"646_CR11","doi-asserted-by":"crossref","unstructured":"Fern\u00e1ndez-Baca D, Slutzki G, Eppstein D (1996) Using sparsification for parametric minimum spanning tree problems. In: Proceedings of the 5th Scandinavian Workshop on Algorithm Theory (SWAT), LNCS, vol 1097, pp 149\u2013160","DOI":"10.1007\/3-540-61422-2_128"},{"issue":"1","key":"646_CR12","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1137\/0218003","volume":"18","author":"G Gallo","year":"1989","unstructured":"Gallo G, Grigoriadis MD, Tarjan RE (1989) A fast parametric maximum flow algorithm and applications. SIAM J Comput 18(1):30\u201355","journal-title":"SIAM J Comput"},{"issue":"2","key":"646_CR13","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1002\/net.20288","volume":"55","author":"E Gassner","year":"2010","unstructured":"Gassner E, Klinz B (2010) A fast parametric assignment algorithm with applications in max-algebra. Networks 55(2):61\u201377","journal-title":"Networks"},{"key":"646_CR14","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/j.ipl.2016.12.003","volume":"120","author":"A Giudici","year":"2017","unstructured":"Giudici A, Halffmann P, Ruzika S, Thielen C (2017) Approximation schemes for the parametric knapsack problem. Inf Process Lett 120:11\u201315","journal-title":"Inf Process Lett"},{"key":"646_CR15","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1002\/net.3230150107","volume":"15","author":"SC Graves","year":"1985","unstructured":"Graves SC, Orlin JB (1985) A minimum concave-cost dynamic network flow problem with an application to lot-sizing. Networks 15:59\u201371","journal-title":"Networks"},{"issue":"5","key":"646_CR16","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1016\/j.orl.2018.07.005","volume":"46","author":"N Halman","year":"2018","unstructured":"Halman N, Holzhauser M, Krumke SO (2018) An FPTAS for the knapsack problem with parametric weights. Oper Res Lett 46(5):487\u2013491","journal-title":"Oper Res Lett"},{"key":"646_CR17","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/j.ipl.2017.06.006","volume":"126","author":"M Holzhauser","year":"2017","unstructured":"Holzhauser M, Krumke SO (2017) An FPTAS for the parametric knapsack problem. Inf Process Lett 126:43\u201347","journal-title":"Inf Process Lett"},{"issue":"1","key":"646_CR18","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/0166-218X(81)90026-3","volume":"3","author":"RM Karp","year":"1981","unstructured":"Karp RM, Orlin JB (1981) Parametric shortest path algorithms with an application to cyclic staffing. Discrete Appl Math 3(1):37\u201345","journal-title":"Discrete Appl Math"},{"key":"646_CR19","volume-title":"Combinatorial optimization: networks and matroids","author":"E Lawler","year":"2001","unstructured":"Lawler E (2001) Combinatorial optimization: networks and matroids. Dover Publications, New York"},{"issue":"5","key":"646_CR20","doi-asserted-by":"publisher","first-page":"744","DOI":"10.1287\/opre.47.5.744","volume":"47","author":"ST McCormick","year":"1999","unstructured":"McCormick ST (1999) Fast algorithms for parametric scheduling come from extensions to parametric maximum flow. Oper Res 47(5):744\u2013756","journal-title":"Oper Res"},{"issue":"3","key":"646_CR21","doi-asserted-by":"publisher","first-page":"663","DOI":"10.1016\/j.ejor.2008.01.007","volume":"194","author":"A Mitsos","year":"2009","unstructured":"Mitsos A, Barton PI (2009) Parametric mixed-integer 0\u20131 linear programming: the general case for a single parameter. Eur J Oper Res 194(3):663\u2013686","journal-title":"Eur J Oper Res"},{"issue":"2","key":"646_CR22","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1006\/jcss.2001.1766","volume":"63","author":"K Mulmuley","year":"2001","unstructured":"Mulmuley K, Shah P (2001) A lower bound for the shortest path problem. J Comput Syst Sci 63(2):253\u2013267","journal-title":"J Comput Syst Sci"},{"issue":"1","key":"646_CR23","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1007\/BF01581642","volume":"19","author":"K Murty","year":"1980","unstructured":"Murty K (1980) Computational complexity of parametric linear programming. Math Program 19(1):213\u2013219","journal-title":"Math Program"},{"key":"646_CR24","doi-asserted-by":"crossref","unstructured":"Nikolova E, Kelner JA, Brand M, Mitzenmacher M (2006) Stochastic shortest paths via quasi-convex maximization. In: Proceedings of the 14th annual European symposium on algorithms (ESA), LNCS, vol 4168, pp 552\u2013563","DOI":"10.1007\/11841036_50"},{"key":"646_CR25","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01585655","volume":"32","author":"JB Orlin","year":"1985","unstructured":"Orlin JB, Rothblum UG (1985) Computing optimal scalings by parametric network algorithms. Math Program 32:1\u201310","journal-title":"Math Program"},{"issue":"1","key":"646_CR26","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1287\/moor.18.1.1","volume":"18","author":"C Papadimitriou","year":"1993","unstructured":"Papadimitriou C, Yannakakis M (1993) The traveling salesman problem with distances one and two. Math Oper Res 18(1):1\u201311","journal-title":"Math Oper Res"},{"issue":"1","key":"646_CR27","first-page":"9","volume":"32","author":"G Ruhe","year":"1988","unstructured":"Ruhe G (1988) Complexity results for multicriterial and parametric network flows using a pathological graph of Zadeh. Z Oper Res 32(1):9\u201327","journal-title":"Z Oper Res"},{"issue":"1","key":"646_CR28","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1287\/moor.16.1.208","volume":"16","author":"H Schneider","year":"1991","unstructured":"Schneider H, Schneider MH (1991) Max-balancing weighted directed graphs and matrix scaling. Math Oper Res 16(1):208\u2013222","journal-title":"Math Oper Res"},{"key":"646_CR29","volume-title":"Combinatorial optimization. Algorithms and combinatorics","author":"A Schrijver","year":"2003","unstructured":"Schrijver A (2003) Combinatorial optimization. Algorithms and combinatorics, vol 24. Springer, Heidelberg"},{"issue":"1","key":"646_CR30","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1007\/s10479-006-0155-z","volume":"150","author":"MG Scutell\u00e0","year":"2007","unstructured":"Scutell\u00e0 MG (2007) A note on the parametric maximum flow problem and some related reoptimization issues. Ann Oper Res 150(1):231\u2013244","journal-title":"Ann Oper Res"},{"issue":"2","key":"646_CR31","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1002\/net.3230210206","volume":"21","author":"NE Young","year":"2006","unstructured":"Young NE, Tarjan RE, Orlin JB (2006) Faster parametric shortest path and minimum-balance algorithms. Networks 21(2):205\u2013221","journal-title":"Networks"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-020-00646-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-020-00646-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-020-00646-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,13]],"date-time":"2022-07-13T17:58:36Z","timestamp":1657735116000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-020-00646-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9,22]]},"references-count":31,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2022,7]]}},"alternative-id":["646"],"URL":"https:\/\/doi.org\/10.1007\/s10878-020-00646-5","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,9,22]]},"assertion":[{"value":"22 September 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}