Maximizing Selection of Overlapping Alternatives
Open Access
- 26 June 2026
- journal article
- Published by Springer Nature in Operations Research Forum
- Vol. 7 (3)
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$$ approximation ratio remains tight in general environments, we show that in a circle-arc environment with alternative length at most $$k$$ items, the baseline greedy guarantees $$3/4$$ , whereas the redundancy-aware algorithm guarantees $$3/4+1/(4k)$$ relative to the optimal solution.
Keywords
Funding Information
- Tel Aviv University
This publication has 10 references indexed in Scilit:
- Improving broadband subsidy allocation: Algorithmic and policy insights from IsraelTelecommunications Policy, 2026
- A refined analysis of submodular GreedyOperations Research Letters, 2021
- Broadband Access as a Public Health Issue: The Role of Law in Expanding Broadband Access and Connecting Underserved Communities for Better Health OutcomesJournal of Law, Medicine & Ethics, 2019
- Broadband Infrastructure and Economic GrowthThe Economic Journal, 2011
- A note on maximizing a submodular set function subject to a knapsack constraintOperations Research Letters, 2004
- Bidding and allocation in combinatorial auctions2000
- The budgeted maximum coverage problemInformation Processing Letters, 1999
- A threshold of ln n for approximating set coverJournal of the ACM, 1998
- Menu Auctions, Resource Allocation, and Economic InfluenceThe Quarterly Journal of Economics, 1986
- An analysis of approximations for maximizing submodular set functions—IMathematical Programming, 1978