APPROXIMATE ALGORITHMS FOR THE MULTIPLE-CHOICE CONTINUOUS KNAPSACK PROBLEMS

DOI10.15807/jorsj.23.28zbMath0426.90059OpenAlexW2729918747MaRDI QIDQ3863692

Toshihide Ibaraki

Publication date: 1980

Published in: Journal of the Operations Research Society of Japan (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.15807/jorsj.23.28

zbMATH Keywords

approximate algorithmsNP-complete problembreadth-1 search methodbreadth-K search methodmultiple-choice continuous knapsack problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Integer programming (90C10) Linear programming (90C05)

Related Items

Branch-and-cut for linear programs with overlapping SOS1 constraints ⋮ The knapsack problem with generalized upper bounds ⋮ A dual approach for the continuous collapsing knapsack problem ⋮ Approximation schemes for deal splitting and covering integer programs with multiplicity constraints ⋮ Robust resource allocations in temporal networks ⋮ An O(n) algorithm for the linear multiple choice knapsack problem and related problems