# 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      