A Proof of Theorem 4.1

In this appendix, we provide the Proof of Theorem 4.1 which is omitted from the main text due to the space limitation. We should point out that the choice of our potential function works best for a combination of k matroids and null = k knapsacks. When the number of matroid and knapsack constraints is not equal, we can always add redundant constraints so that k is the maximum of the two numbers. For this reason, in the rest of this proof, we assume null = k . Then, we always have φ (S a) φ (S) with γ (S a) < 1. Proof.