On inner independence systems

A classic result of Korte and Hausmann [1978] and Jenkyns [1976] bounds the quality of the greedy solution to the problem of finding a maximum value basis of an independence system (E,ℐ)$$ \left(E,\mathcal{I}\right) $$in terms of the rank‐quotient. We extend this result in two ways. First, we apply the greedy algorithm to an inner independence system contained in ℐ$$ \mathcal{I} $$. Additionally, following an idea of Milgrom [2017], we incorporate exogenously given prior information about the set of likely candidates for an optimal basis in terms of a set 𝒪⊆ℐ. We provide a generalization of the rank‐quotient that yields a tight bound on the worst‐case performance of the greedy algorithm applied to the inner independence system relative to the optimal solution in 𝒪. Furthermore, we show that for a worst‐case objective, the inner independence system approximation may outperform not only the standard greedy algorithm but also the inner matroid approximation proposed by Milgrom [2017]. Second, we generalize the inner approximation framework of independence systems to inner approximations of packing instances in ℤ≥0n$$ {\mathbb{Z}}_{\ge 0}^n $$by inner polymatroids and inner packing instances. We consider the problem of maximizing a separable discrete concave function and show that our inner approximation can be better than the greedy algorithm applied to the original packing instance. Our result provides a lower bound to the generalized rank‐quotient of a greedy algorithm to the optimal solution in this more general setting and subsumes Malinov and Kovalyov [1980]. We apply the inner approximation approach to packing instances induced by the FCC incentive auction and by two knapsack constraints.