Maximizing Selection of Overlapping Alternatives

This paper introduces redundancy-aware greedy algorithms for the cardinality- and budget-constrained maximum coverage problems. Unlike classical greedy procedures, our approach identifies and removes previously selected alternatives that become redundant as new selections are added, thereby freeing capacity or budget for additional selection. To demonstrate practical utility, we analyze an Israel-based broadband infrastructure deployment procurement auction. Our results show that the redundancy-aware algorithm increases the number of connected households while reducing redundant households in overlap areas and approaching the LP-relaxation upper bound. Finally, while the general 1-1/e ≈ 0.632 1 - 1 / e ≈ 0.632 approximation ratio remains tight in general environments, we show that in a circle-arc environment with alternative length at most k k items, the baseline greedy guarantees $$3/4$$ 3 / 4 , whereas the redundancy-aware algorithm guarantees $$3/4+1/(4k)$$ 3 / 4 + 1 / ( 4 k ) relative to the optimal solution.