{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,13]],"date-time":"2026-05-13T11:27:02Z","timestamp":1778671622261,"version":"3.51.4"},"reference-count":47,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2022,8,30]],"date-time":"2022-08-30T00:00:00Z","timestamp":1661817600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,8,30]],"date-time":"2022-08-30T00:00:00Z","timestamp":1661817600000},"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":["398572517"],"award-info":[{"award-number":["398572517"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"crossref","award":["398572517"],"award-info":[{"award-number":["398572517"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2022,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In a widely-studied class of multi-parametric optimization problems, the objective value of each solution is an affine function of real-valued parameters. Then, the goal is to provide an optimal solution set, i.e., a set containing an optimal solution for each non-parametric problem obtained by fixing a parameter vector. For many multi-parametric optimization problems, however, an optimal solution set of minimum cardinality can contain super-polynomially many solutions. Consequently, no polynomial-time exact algorithms can exist for these problems even if<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\textsf {P}=\\textsf {NP}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>P<\/mml:mi><mml:mo>=<\/mml:mo><mml:mi>NP<\/mml:mi><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>. We propose an approximation method that is applicable to a general class of multi-parametric optimization problems and outputs a set of solutions with cardinality polynomial in the instance size and the inverse of the approximation guarantee. This method lifts approximation algorithms for non-parametric optimization problems to their parametric version and provides an approximation guarantee that is arbitrarily close to the approximation guarantee of the approximation algorithm for the non-parametric problem. If the non-parametric problem can be solved exactly in polynomial time or if an FPTAS is available, our algorithm is an FPTAS. Further, we show that, for any given approximation guarantee, the minimum cardinality of an approximation set is, in general, not<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\ell $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>\u2113<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-approximable for any natural number\u00a0<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\ell $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>\u2113<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>less or equal to the number of parameters, and we discuss applications of our results to classical multi-parametric combinatorial optimizations problems. In particular, we obtain an FPTAS for the multi-parametric minimum<jats:italic>s<\/jats:italic>-<jats:italic>t<\/jats:italic>-cut problem, an FPTAS for the multi-parametric knapsack problem, as well as an approximation algorithm for the multi-parametric maximization of independence systems problem.<\/jats:p>","DOI":"10.1007\/s10878-022-00902-w","type":"journal-article","created":{"date-parts":[[2022,8,30]],"date-time":"2022-08-30T22:11:41Z","timestamp":1661897501000},"page":"1459-1494","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["An approximation algorithm for a general class of multi-parametric optimization problems"],"prefix":"10.1007","volume":"44","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6588-5266","authenticated-orcid":false,"given":"Stephan","family":"Helfrich","sequence":"first","affiliation":[]},{"given":"Arne","family":"Herzel","sequence":"additional","affiliation":[]},{"given":"Stefan","family":"Ruzika","sequence":"additional","affiliation":[]},{"given":"Clemens","family":"Thielen","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,8,30]]},"reference":[{"issue":"1\u20132","key":"902_CR1","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s10107-015-0944-8","volume":"154","author":"H Aissi","year":"2015","unstructured":"Aissi H, Mahjoub AR, McCormick ST, Queyranne M (2015) Strongly polynomial bounds for multiobjective and parametric global minimum cuts in graphs and hypergraphs. Math Program 154(1\u20132):3\u201328","journal-title":"Math Program"},{"issue":"1","key":"902_CR2","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1016\/j.orl.2021.12.009","volume":"50","author":"M Allman","year":"2022","unstructured":"Allman M, Lo V, McCormick ST (2022) Complexity of source-sink monotone 2-parameter min cut. Oper Res Lett 50(1):84\u201390","journal-title":"Oper Res Lett"},{"key":"902_CR3","doi-asserted-by":"publisher","first-page":"1328","DOI":"10.1007\/s10878-020-00646-5","volume":"43","author":"C Bazgan","year":"2022","unstructured":"Bazgan C, Herzel A, Ruzika S, Thielen C, Vanderpooten D (2022) An approximation algorithm for a general class of parametric optimization problems. J Comb Optim 43:1328\u20131358","journal-title":"J Comb Optim"},{"key":"902_CR4","unstructured":"Carstensen PJ (1983a) The complexity of some problems in parametric, linear, and combinatorial programming. PhD thesis, University of Michigan"},{"issue":"1","key":"902_CR5","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1007\/BF02591893","volume":"26","author":"PJ Carstensen","year":"1983","unstructured":"Carstensen PJ (1983b) Complexity of some parametric integer and network programming problems. Math Program 26(1):64\u201375","journal-title":"Math Program"},{"issue":"3","key":"902_CR6","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":"902_CR7","unstructured":"Diakonikolas I (2011) Approximation of multiobjective optimization problems. PhD thesis, Columbia University"},{"key":"902_CR8","unstructured":"Diakonikolas I, Yannakakis M (2008) Succinct approximate convex Pareto curves. In: Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, pp 74\u201383"},{"issue":"11","key":"902_CR9","doi-asserted-by":"publisher","first-page":"1565","DOI":"10.1287\/mnsc.42.11.1565","volume":"42","author":"M Eben-Chaime","year":"1996","unstructured":"Eben-Chaime M (1996) Parametric solution for linear bicriteria knapsack models. Manag Sci 42(11):1565\u20131575","journal-title":"Manag Sci"},{"key":"902_CR10","first-page":"817","volume-title":"Exact methods for multi-objective combinatorial optimisation","author":"M Ehrgott","year":"2016","unstructured":"Ehrgott M, Gandibleux X, Przybylski A (2016) Exact methods for multi-objective combinatorial optimisation. Springer, New York, pp 817\u2013850"},{"issue":"4","key":"902_CR11","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":"902_CR12","doi-asserted-by":"crossref","unstructured":"Erickson J (2010) Maximum flows and parametric shortest paths in planar graphs. In: Proceedings of the 21st ACM-SIAM symposium on discrete algorithms (SODA), pp 794\u2013804","DOI":"10.1137\/1.9781611973075.65"},{"key":"902_CR13","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), pp 149\u2013160","DOI":"10.1007\/3-540-61422-2_128"},{"key":"902_CR14","doi-asserted-by":"crossref","unstructured":"Fern\u00e1ndez-Baca D, Sepp\u00e4l\u00e4inen T, Slutzki G (2000) Parametric multiple sequence alignment and phylogeny construction. In: Combinatorial pattern matching. Springer Berlin Heidelberg, pp 69\u201383","DOI":"10.1007\/3-540-45123-4_8"},{"issue":"7","key":"902_CR15","doi-asserted-by":"publisher","first-page":"406","DOI":"10.1287\/mnsc.18.7.406","volume":"18","author":"T Gal","year":"1972","unstructured":"Gal T, Nedoma J (1972) Multiparametric linear programming. Manag Sci 18(7):406\u2013422","journal-title":"Manag Sci"},{"issue":"1","key":"902_CR16","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":"4","key":"902_CR17","first-page":"395","volume":"3","author":"S Gass","year":"1955","unstructured":"Gass S, Saaty T (1955) Parametric objective function (part 2)\u2014generalization. J Oper Res Soc Am 3(4):395\u2013401","journal-title":"J Oper Res Soc Am"},{"issue":"2","key":"902_CR18","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":"902_CR19","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":"902_CR20","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"},{"key":"902_CR21","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-78240-4","volume-title":"Geometric algorithms and combinatorial optimization","author":"M Gr\u00f6tschel","year":"1993","unstructured":"Gr\u00f6tschel M, Lov\u00e1sz L, Schrijver A (1993) Geometric algorithms and combinatorial optimization. Springer"},{"issue":"5","key":"902_CR22","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":"902_CR23","unstructured":"Helfrich S, Herzel A, Ruzika S, Thielen C (2021) Approximating biobjective minimization problems using general ordering cones. arXiv:2109.10067"},{"issue":"4","key":"902_CR24","first-page":"1284","volume":"33","author":"A Herzel","year":"2021","unstructured":"Herzel A, Ruzika S, Thielen C (2021) Approximation methods for multiobjective optimization problems: a survey. INFORMS J Comput 33(4):1284\u20131299","journal-title":"INFORMS J Comput"},{"key":"902_CR25","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"},{"key":"902_CR26","doi-asserted-by":"crossref","unstructured":"Karger DR (2016) Enumerating parametric global minimum cuts by random interleaving. In: Proceedings of the 48th ACM symposium on the theory of computing (STOC), pp 542\u2013555","DOI":"10.1145\/2897518.2897578"},{"issue":"1","key":"902_CR27","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"},{"issue":"1","key":"902_CR28","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1023\/A:1009813105532","volume":"3","author":"H Kellerer","year":"1999","unstructured":"Kellerer H, Pferschy U (1999) A new fully polynomial time approximation scheme for the knapsack problem. J Comb Optim 3(1):59\u201371","journal-title":"J Comb Optim"},{"key":"902_CR29","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1023\/B:JOCO.0000021934.29833.6b","volume":"8","author":"H Kellerer","year":"2004","unstructured":"Kellerer H, Pferschy U (2004) Improved dynamic programming in connection with an FPTAS for the knapsack problem. J Comb Optim 8:5\u201311","journal-title":"J Comb Optim"},{"key":"902_CR30","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24777-7","volume-title":"Knapsack problems","author":"H Kellerer","year":"2004","unstructured":"Kellerer H, Pferschy U, Pisinger D (2004) Knapsack problems. Springer"},{"key":"902_CR31","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/S0167-5060(08)70322-4","volume":"2","author":"B Korte","year":"1978","unstructured":"Korte B, Hausmann D (1978) An analysis of the greedy heuristic for independence systems. Ann Discrete Math 2:65\u201374","journal-title":"Ann Discrete Math"},{"issue":"5","key":"902_CR32","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"},{"key":"902_CR33","doi-asserted-by":"crossref","unstructured":"Mestre J (2006) Greedy in approximation algorithms. In: Proceedings of the 14th Annual European Symposium on Algorithms (ESA), LNCS, vol 4168 , pp 528\u2013539","DOI":"10.1007\/11841036_48"},{"issue":"2","key":"902_CR34","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"},{"key":"902_CR35","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":"902_CR36","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/j.cherd.2016.09.034","volume":"116","author":"R Oberdieck","year":"2016","unstructured":"Oberdieck R, Diangelakis NA, Nascu I, Papathanasiou MM, Sun M, Avraamidou S, Pistikopoulos EN (2016) On multi-parametric programming and its applications in process systems engineering. Chem Eng Res Des 116:61\u201382","journal-title":"Chem Eng Res Des"},{"key":"902_CR37","doi-asserted-by":"crossref","unstructured":"Orlin JB (2013) Max flows in $${\\cal{O}}(nm)$$ time, or better. In: Proceedings of the 45th ACM symposium on the theory of computing (STOC), pp 765\u2013774","DOI":"10.1145\/2488608.2488705"},{"key":"902_CR38","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"},{"key":"902_CR39","doi-asserted-by":"crossref","unstructured":"Papadimitriou C, Yannakakis M (2000) On the approximability of trade-offs and optimal access of web sources. In: Proceedings of the 41st annual IEEE symposium on the foundations of computer science (FOCS), pp 86\u201392","DOI":"10.1109\/SFCS.2000.892068"},{"issue":"2","key":"902_CR40","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1007\/s10287-012-0144-4","volume":"9","author":"EN Pistikopoulos","year":"2012","unstructured":"Pistikopoulos EN, Dominguez L, Panos C, Kouramas K, Chinchuluun A (2012) Theoretical and algorithmic advances in multi-parametric programming and control. Comput Manag Sci 9(2):183\u2013203","journal-title":"Comput Manag Sci"},{"issue":"1","key":"902_CR41","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":"3","key":"902_CR42","first-page":"316","volume":"2","author":"T Saaty","year":"1954","unstructured":"Saaty T, Gass S (1954) Parametric objective function (part 1). J Oper Res Soc Am 2(3):316\u2013319","journal-title":"J Oper Res Soc Am"},{"issue":"1","key":"902_CR43","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 HM (1991) Max-balancing weighted directed graphs and matrix scaling. Math Oper Res 16(1):208\u2013222","journal-title":"Math Oper Res"},{"key":"902_CR44","unstructured":"Seipp F (2013) On adjacency, cardinality, and partial dominance in discrete multiple objective optimization. PhD thesis, TU Kaiserslautern"},{"issue":"2\u20133","key":"902_CR45","doi-asserted-by":"publisher","first-page":"334","DOI":"10.1016\/j.tcs.2005.09.022","volume":"348","author":"S Vassilvitskii","year":"2005","unstructured":"Vassilvitskii S, Yannakakis M (2005) Efficiently computing succinct trade-off curves. Theoret Comput Sci 348(2\u20133):334\u2013356","journal-title":"Theoret Comput Sci"},{"key":"902_CR46","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511921735","volume-title":"The design of approximation algorithms","author":"DP Williamson","year":"2011","unstructured":"Williamson DP, Shmoys DB (2011) The design of approximation algorithms. Cambridge University Press"},{"issue":"2","key":"902_CR47","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-022-00902-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-022-00902-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-022-00902-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,16]],"date-time":"2023-02-16T17:03:57Z","timestamp":1676567037000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-022-00902-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,30]]},"references-count":47,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,10]]}},"alternative-id":["902"],"URL":"https:\/\/doi.org\/10.1007\/s10878-022-00902-w","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,8,30]]},"assertion":[{"value":"20 August 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 August 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}]}}