Online algorithms for the maximum k-interval coverage problem

Abstract

<p></p><p>We study the online maximum coverage problem on a target interval, in which, given an online sequence of sub-intervals (which may intersect among each other) to arrive, we aim to select at most k of the sub-intervals such that the total covered length of the target interval is maximized. The decision to accept or reject each sub-interval is made immediately and irrevocably right at the release time of the sub-interval. We comprehensively study various settings of this problem regarding both the length of each released sub-interval and the total number of released sub-intervals. To begin with, we investigate the offline version of the problem where the sequence of all the released sub-intervals is known in advance to the decision-maker and propose two polynomial-time optimal solutions to different settings of our offline problem. For the online problem, lower bounds on the competitive ratio are first proposed on our well-designed release schemes of sub-intervals. Then, we propose a Single-threshOld-based deterministic Algorithm (SOA), which adds a sub-interval if the added length without overlap exceeds a certain threshold, achieving competitive ratios close to the lower bounds. Further, we extend SOA to a Double-threshOlds-based deterministic Algorithm (DOA) by using the first threshold for exploration and the second threshold (larger than the first one) for exploitation. With the two thresholds generated by our proposed program, we show that DOA outperforms SOA slightly in the worst-case scenario. Moreover, we show that more thresholds cannot induce better worst-case performance of an online deterministic algorithm as long as those thresholds are used in non-increasing order in accepting sub-intervals.<br></p>