.png){kind=icon}
.png){kind=icon}
Return
Efficient algorithms for the interval maximum coverage problem
.png){kind=icon}
PRE
AI
DOI：10.1016/j.tcs.2026.115802.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
This paper studies a special case of the Maximum Interval Multi-Cover (MaxIMC) problem, called the Interval Maximum Coverage Problem. Given a set of points P on the real line, a collection of intervals I, and a budget K, the goal is to select up to K intervals that maximize the number of covered points. While the computational complexity of the general MaxIMC problem with arbitrary coverage requirements remains open, this special case admits efficient polynomial-time solutions. We develop an exact algorithm that improves computational efficiency when the number of intervals is extremely large, and a near-linear-time approximation algorithm for the case where each interval covers exactly r points. We provide formal proofs of correctness, detailed complexity analysis, and experimental results demonstrating the practical efficiency and effectiveness of the proposed algorithms.
Keywords:
Interval covering
Approximation algorithms
Dynamic programming
Greedy algorithms
Combinatorial optimization