Maximizing Selection of Overlapping Alternatives

Abstract 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 \approx 0.632$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>1</mml:mn> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> <mml:mo>/</mml:mo> <mml:mi>e</mml:mi> <mml:mo>≈</mml:mo> <mml:mn>0.632</mml:mn> </mml:mrow> </mml:math> approximation ratio remains tight in general environments, we show that in a circle-arc environment with alternative length at most $$k$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>k</mml:mi> </mml:math> items, the baseline greedy guarantees $$3/4$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>3</mml:mn> <mml:mo>/</mml:mo> <mml:mn>4</mml:mn> </mml:mrow> </mml:math> , whereas the redundancy-aware algorithm guarantees $$3/4+1/(4k)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>3</mml:mn> <mml:mo>/</mml:mo> <mml:mn>4</mml:mn> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> <mml:mo>/</mml:mo> <mml:mo>(</mml:mo> <mml:mn>4</mml:mn> <mml:mi>k</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> relative to the optimal solution.