{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,30]],"date-time":"2025-05-30T06:23:55Z","timestamp":1748586235498,"version":"3.37.3"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,4,27]],"date-time":"2022-04-27T00:00:00Z","timestamp":1651017600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,4,27]],"date-time":"2022-04-27T00:00:00Z","timestamp":1651017600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100003977","name":"israel science foundation","doi-asserted-by":"publisher","award":["399\/17"],"award-info":[{"award-number":["399\/17"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006221","name":"united states - israel binational science foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006221","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["4OR-Q J Oper Res"],"published-print":{"date-parts":[[2023,6]]},"DOI":"10.1007\/s10288-022-00509-1","type":"journal-article","created":{"date-parts":[[2022,4,27]],"date-time":"2022-04-27T14:04:33Z","timestamp":1651068273000},"page":"235-246","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Max\u2013max, max\u2013min, min\u2013max and min\u2013min knapsack problems with a parametric constraint"],"prefix":"10.1007","volume":"21","author":[{"given":"Nir","family":"Halman","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0832-0829","authenticated-orcid":false,"given":"Mikhail Y.","family":"Kovalyov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alain","family":"Quilliot","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,4,27]]},"reference":[{"key":"509_CR1","doi-asserted-by":"crossref","unstructured":"Agarwal P, Eppstein D, Guibas L, Henzinger M (1998) Parametric and kinetic minimum spanning trees. In: 39th annual symposium on foundations of computer science, 1998. Proceedings. IEEE, pp 596\u2013605","DOI":"10.1109\/SFCS.1998.743510"},{"issue":"1","key":"509_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. Discret Appl Math 41(1):69\u201374","journal-title":"Discret Appl Math"},{"key":"509_CR3","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-020-00646-5","author":"C Bazgan","year":"2020","unstructured":"Bazgan C, Herzel A, Ruzika S, Thielen C, Vanderpooten D (2020) An approximation algorithm for a general class of parametric optimization problems. J Combin Optim. https:\/\/doi.org\/10.1007\/s10878-020-00646-5","journal-title":"J Combin Optim"},{"key":"509_CR4","unstructured":"Carstensen PJ (1983a) The complexity of some problems in parametric, linear, and combinatorial programming. Ph.d. thesis, University of Michigan"},{"issue":"1","key":"509_CR5","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1007\/BF02591893","volume":"26","author":"PJ Carstensen","year":"1983","unstructured":"Carstensen PJ (1983) Complexity of some parametric integer and network programming problems. Math Program 26(1):64\u201375","journal-title":"Math Program"},{"issue":"11","key":"509_CR6","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":"509_CR7","doi-asserted-by":"crossref","unstructured":"Fern\u00e1ndez-Baca DF, Slutzki G, Eppstein D (1996) Using sparsification for parametric minimum spanning tree problems. In: Proceedings of the 5th Scandinavian workshop on algorithm theory, SWAT. Lecture Notes in Computer Science, vol 1097, pp 149\u2013160","DOI":"10.1007\/3-540-61422-2_128"},{"key":"509_CR8","volume-title":"Postoptimal analyses, parametrie programming, and related topics: degeneracy, multicriteria decision making, redundancy","author":"T Gal","year":"1995","unstructured":"Gal T (1995) Postoptimal analyses, parametrie programming, and related topics: degeneracy, multicriteria decision making, redundancy, 2nd edn. Walter de Gruyter, Berlin, New York","edition":"2"},{"issue":"1","key":"509_CR9","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"},{"key":"509_CR10","volume-title":"Computers and intractability: a guide to the theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. W.H. Freeman and Co., San Francisco"},{"issue":"2","key":"509_CR11","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":"509_CR12","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":"509_CR13","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:487\u2013491","journal-title":"Oper Res Lett"},{"key":"509_CR14","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":"509_CR15","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. Discret Appl Math 3(1):37\u201345","journal-title":"Discret Appl Math"},{"issue":"5","key":"509_CR16","doi-asserted-by":"publisher","first-page":"744","DOI":"10.1287\/opre.47.5.744","volume":"47","author":"S McCormick","year":"1999","unstructured":"McCormick S (1999) Fast algorithms for parametric scheduling come from extensions to parametric maximum flow. Oper Res 47(5):744\u2013756","journal-title":"Oper Res"},{"issue":"4","key":"509_CR17","doi-asserted-by":"publisher","first-page":"414","DOI":"10.1287\/moor.4.4.414","volume":"4","author":"N Megiddo","year":"1979","unstructured":"Megiddo N (1979) Combinatorial optimization with rational objective functions. Math Oper Res 4(4):414\u2013424","journal-title":"Math Oper Res"},{"issue":"2","key":"509_CR18","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":"509_CR19","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:213\u2013219","journal-title":"Math Program"},{"issue":"1","key":"509_CR20","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":"509_CR21","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1007\/BF02022047","volume":"4","author":"IS Schubert","year":"1985","unstructured":"Schubert IS, Zimmermann U (1985) One-parametric bottleneck transportation problems. Ann Oper Res 4(1):343\u2013369","journal-title":"Ann Oper Res"},{"issue":"1","key":"509_CR22","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1007\/s10479-006-0155-z","volume":"150","author":"M Scutella","year":"2007","unstructured":"Scutella M (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":"509_CR23","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"},{"issue":"5","key":"509_CR24","first-page":"187","volume":"29","author":"U Zimmermann","year":"1985","unstructured":"Zimmermann U, Schubert IS (1985) Nonlinear one-parametric bottleneck linear programming. Z Oper Res 29(5):187\u2013201","journal-title":"Z Oper Res"}],"container-title":["4OR"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10288-022-00509-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10288-022-00509-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10288-022-00509-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,11]],"date-time":"2023-05-11T06:58:43Z","timestamp":1683788323000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10288-022-00509-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,4,27]]},"references-count":24,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,6]]}},"alternative-id":["509"],"URL":"https:\/\/doi.org\/10.1007\/s10288-022-00509-1","relation":{},"ISSN":["1619-4500","1614-2411"],"issn-type":[{"type":"print","value":"1619-4500"},{"type":"electronic","value":"1614-2411"}],"subject":[],"published":{"date-parts":[[2022,4,27]]},"assertion":[{"value":"27 July 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 March 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 April 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 April 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"All authors certify that there is no actual or potential conflict of interest in relation to this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}