Max-max, max-min, min-max and min-min knapsack problems with a parametric constraint

被引：0

作者：

Halman, Nir ^{[1
]}

Kovalyov, Mikhail Y. ^{[2
]}

Quilliot, Alain ^{[3
]}

机构：

[1] Bar Ilan Univ, Ramat Gan, Israel

[2] Natl Acad Sci Belarus, United Inst Informat Problems, Minsk, BELARUS

[3] Univ Blaise Pascal, UMR CNRS 6158, LIMOS, Bat ISIMA,Campus Cezeaux,BP 125, F-63173 Aubiere, France

来源：

4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH | 2023年 / 21卷 / 02期

基金：

以色列科学基金会;

关键词：

Knapsack problems; Parametric optimization; Polynomial algorithm; FPTAS; ALGORITHMS; COMPLEXITY; FPTAS;

D O I：

10.1007/s10288-022-00509-1

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

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) and 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) 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.

引用

页码：235 / 246

页数：12

共 24 条

[1]

Agarwal P, 1998, 39 ANN S FDN COMPUTE

[2] GENERALIZATION OF A THEOREM ON THE PARAMETRIC MAXIMUM FLOW PROBLEM [J].