Max–max, max–min, min–max and min–min knapsack problems with a parametric constraint
Nir Halman (),
Mikhail Y. Kovalyov () and
Alain Quilliot ()
Additional contact information
Nir Halman: Bar-Ilan University
Mikhail Y. Kovalyov: National Academy of Sciences of Belarus
Alain Quilliot: Université Blaise Pascal
4OR, 2023, vol. 21, issue 2, No 3, 235-246
Abstract:
Abstract Max–max, max–min, min–max and min–min optimization problems with a knapsack-type constraint containing a single numerical parameter are studied. The goal is to present optimal solutions for all possible values of the parameter. Algorithms with $$O(n\log n)$$ O ( n log n ) and $$O(n^2)$$ O ( n 2 ) running times are proposed for the problems with a fixed parameter and for the general problem, respectively, where n is the number of items to be packed into the knapsack. The latter algorithm determines optimal solution values for all values of the parameter in $$O(n\log ^2 n)$$ O ( n log 2 n ) time. The problem of deciding whether there exists a single optimal solution for all values of the numerical parameter is proved to be NP-complete.
Keywords: Knapsack problems; Parametric optimization; Polynomial algorithm; FPTAS; 90C31; 68Q25; 68Q17; 90C59 (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:
Downloads: (external link)
http://link.springer.com/10.1007/s10288-022-00509-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.
Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.
Export reference: BibTeX
RIS (EndNote, ProCite, RefMan)
HTML/Text
Persistent link: https://EconPapers.repec.org/RePEc:spr:aqjoor:v:21:y:2023:i:2:d:10.1007_s10288-022-00509-1
Ordering information: This journal article can be ordered from
https://www.springer ... ch/journal/10288/PSE
DOI: 10.1007/s10288-022-00509-1
Access Statistics for this article
4OR is currently edited by Yves Crama, Michel Grabisch and Silvano Martello
More articles in 4OR from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().