Online algorithms for the maximum k-interval coverage problem

DOI10.1007/S10878-022-00898-3MaRDI QIDQ2091105zbMATH OpenOpenAlexWikidataFDO

Authors Minming Li, Lingjie Duan, Victor C. S. Lee, Songhua Li

Publication date 31 October 2022

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2011.10938

zbMATH Keywords

online algorithminterval coveragemaximum \(k\)-coverage problemonline budgeted maximum coverage problem

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Abstract: We study the online maximum coverage problem on a line, in which, given an online sequence of sub-intervals (which may intersect among each other) of a target large interval and an integer $k$, 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 (no preemption) right at the release timestamp of the sub-interval. We comprehensively study different settings of this problem regarding both the length of a released sub-interval and the total number of released sub-intervals. We first present lower bounds on the competitive ratio for the settings concerned in this paper, respectively. For the offline problem where the sequence of all the released sub-intervals is known in advance to the decision-maker, we propose a dynamic-programming-based optimal approach as the benchmark. For the online problem, we first propose a single-threshold-based deterministic algorithm SOA by adding a sub-interval if the added length exceeds a certain threshold, achieving competitive ratios close to the lower bounds, respectively. Then, we extend to a double-thresholds-based algorithm DOA, by using the first threshold for exploration and the second threshold (larger than the first one) for exploitation. With the two thresholds solved by our proposed program, we show that DOA improves SOA in the worst-case performance. Moreover, we prove that a deterministic algorithm that accepts sub-intervals by multi non-increasing thresholds cannot outperform even SOA.

Recommendations

• Online maximum \(k\)-coverage
• Online maximum \(k\)-coverage
• scientific article; zbMATH DE number 1003261
• Online budgeted maximum coverage
• Online selection of intervals and t-intervals

Cites work

• scientific article; zbMATH DE number 1323125 (Why is no real title available?)
• scientific article; zbMATH DE number 2086630 (Why is no real title available?)
• A Knapsack Secretary Problem with Applications
• A framework for the secretary problem on the intersection of matroids
• A multiple-choice secretary algorithm with applications to online auctions
• Can the Measure of ∪ n 1 [ a i , b i ] be Computed in Less Than O(n logn) Steps?
• New results for the \(k\)-secretary problem
• On interval and circular-arc covering problems
• Online Scheduling of Equal‐Length Jobs: Randomization and Restarts Help
• Online budgeted maximum coverage
• Online competitive algorithms for maximizing weighted throughput of unit jobs
• Online maximum \(k\)-coverage
• Online maximum \(k\)-interval coverage problem
• Online submodular maximization with preemption
• Submodular secretary problem and extensions
• The budgeted maximum coverage problem
• The online set cover problem
• The submodular secretary problem goes linear
• Tight bounds for single-pass streaming complexity of the set cover problem

Cited in

(5)

• Mean analysis of an online algorithm for the vertex cover problem
• Online maximum \(k\)-coverage
• scientific article; zbMATH DE number 6905172 (Why is no real title available?)
• Online k-max Search Algorithms with Applications to the Secretary Problem
• Online maximum \(k\)-interval coverage problem

This page was built for publication: Online algorithms for the maximum \(k\)-interval coverage problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2091105)