On inner independence systems - Sven de Vries; Stephen Raach; Rakesh V. Vohra (Naval Research Logistics (NRL), 2024)
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,ℐ) (E,I) 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 ℐ 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 Z_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.
Keywords: 650; greedy algorithm; independence systems; inner approximation; packing problems