Online Maximum k-Interval Coverage Problem

Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45)32_Refereed conference paper (with ISBN/ISSN)peer-review

View graph of relations

Related Research Unit(s)

Detail(s)

Original languageEnglish
Title of host publicationCombinatorial Optimization and Applications
Subtitle of host publication14th International Conference, COCOA 2020, Proceedings
EditorsWeili Wu, Zhongnan Zhang
PublisherSpringer Nature
Pages455-470
ISBN (Electronic)978-3-030-64843-5
ISBN (Print)978-3-030-64842-8
Publication statusPublished - Dec 2020

Publication series

NameLecture Notes in Computer Science (including subseries Theoretical Computer Science and General Issues)
Volume12577
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Title14th International Conference on Combinatorial Optimization and Applications, COCOA 2020
LocationVirtual
PlaceUnited States
CityDallas
Period11 - 13 December 2020

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 the problem, regarding the number of total released sub-intervals, we consider the unique-number (UN) setting where the total number is known in advance and the arbitrary-number (AN) setting where the total number is not known, respectively; regarding the length of a released sub-interval, we generally consider three settings: each sub-interval is of a normalized unit-length (UL), a flexible-length (FL) in a known range, or an arbitrary-length (AL). In addition, we extend the UL setting to a generalized unit-sum (US) setting, where a batch of a finite number of disjoint sub-intervals of the unit total length is released instead at each timestamp, and accordingly k batches can be accepted. We first prove in the AL setting that no online deterministic algorithm can achieve a bounded competitive ratio. Then, we present lower bounds on the competitive ratio for the other settings concerned in this paper. 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.

Research Area(s)

  • Budgeted maximum coverage problem, Interval coverage, Maximum k-coverage problem, Online algorithm

Bibliographic Note

Full text of this publication does not contain sufficient affiliation information. With consent from the author(s) concerned, the Research Unit(s) information for this record is based on the existing academic department affiliation of the author(s).

Citation Format(s)

Online Maximum k-Interval Coverage Problem. / Li, Songhua; Li, Minming; Duan, Lingjie; Lee, Victor C. S.

Combinatorial Optimization and Applications: 14th International Conference, COCOA 2020, Proceedings. ed. / Weili Wu; Zhongnan Zhang. Springer Nature, 2020. p. 455-470 (Lecture Notes in Computer Science (including subseries Theoretical Computer Science and General Issues); Vol. 12577).

Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45)32_Refereed conference paper (with ISBN/ISSN)peer-review