Multi-constrained matroidal knapsack problems

The paper considers 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 it proves that Lagrengean 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.