ZIB

Hits per page

hit 1 - 1 | 1 hit

Sorting

Electronic Resource

Multi-constrained matroidal knapsack problems (1989)

Camerini, P. M. ; Maffioli, F. ; Vercellis, C.

Springer

Mathematical programming 45 (1989), S. 211-231

add to mindlist on the mindlist

Details

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

Library	Location	Call Number	Volume/Issue/Year	Availability

Others were also interested in ...

Paper (German National Licenses)

Fulltext

hit 1 - 1 | 1 hit