ISSN:
1436-4646
Keywords:
Knapsack
;
matroids
;
asymptotically optimum bounds
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract We consider multi-constrained knapsack problems where the sets of elements to be selected are subject to combinatorial constraints of matroidal nature. For this important class of NP-hard combinatorial optimization problems we prove that Lagrangean relaxation techniques not only provide good bounds to the value of the optimum, but also yield approximate solutions, which are asymptotically optimal under mild probabilistic assumptions.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01589104
Permalink