New polynomial bounds for matroidal knapsacks

The Matroidal Knapsack Problem (MK) consists in finding the maximum weight basis for a given matroid subject to a knapsack constraint. Special cases of this problem are the Multiple Choice Knapsack and the Capacitated Minimal Spanning Tree Problems. Using matroidal relaxations for knapsack problems we build a relaxation for MK. This relaxation produces an upper bound on MK dominating the usual LP-bound and computable using a polynomial number of calls to the greedy algorithm for the matroid.