ISSN:
1436-4646
Keywords:
Concave functions
;
knapsack problems
;
strict minimizers
;
NP-hard
;
nonconvex
;
local minimizers
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract We consider a version of the knapsack problem which gives rise to a separable concave minimization problem subject to bounds on the variables and one equality constraint. We characterize strict local miniimizers of concave minimization problems subject to linear constraints, and use this characterization to show that although the problem of determining a global minimizer of the concave knapsack problem is NP-hard, it is possible to determine a local minimizer of this problem with at most O(n logn) operations and 1+[logn] evaluations of the function. If the function is quadratic this algorithm requires at most O(n logn) operations.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01588800
Permalink
