# Max–max, max–min, min–max and min–min knapsack problems with a parametric constraint

Max–max, max–min, min–max and min–min knapsack problems with a parametric constraint 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(nlogn)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$O(n\log n)$$\end{document} and O(n2)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$O(n^2)$$\end{document} 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(nlog2n)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$O(n\log ^2 n)$$\end{document} 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. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png 4OR Springer Journals

# Max–max, max–min, min–max and min–min knapsack problems with a parametric constraint

, Volume 21 (2) – Jun 1, 2023
12 pages

/lp/springer-journals/max-max-max-min-min-max-and-min-min-knapsack-problems-with-a-MtW8JsdH23

# References (27)

Publisher
Springer Journals
Copyright © The Author(s), under exclusive licence to Springer-Verlag GmbH Germany, part of Springer Nature 2022
ISSN
1619-4500
eISSN
1614-2411
DOI
10.1007/s10288-022-00509-1
Publisher site
See Article on Publisher Site

### 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(nlogn)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$O(n\log n)$$\end{document} and O(n2)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$O(n^2)$$\end{document} 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(nlog2n)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$O(n\log ^2 n)$$\end{document} 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.

### Journal

4ORSpringer Journals

Published: Jun 1, 2023

Keywords: Knapsack problems; Parametric optimization; Polynomial algorithm; FPTAS; 90C31; 68Q25; 68Q17; 90C59