Fotakis, Dimitris ;
Kavouras, Loukas ;
Koumoutsos, Grigorios ;
Skoulakis, Stratis ;
Vardas, Manolis
The Online MinSum Set Cover Problem
Abstract
We consider the online MinSum Set Cover (MSSC), a natural and intriguing generalization of the classical list update problem. In Online MSSC, the algorithm maintains a permutation on n elements based on subsets S₁, S₂, … arriving online. The algorithm serves each set S_t upon arrival, using its current permutation π_t, incurring an access cost equal to the position of the first element of S_t in π_t. Then, the algorithm may update its permutation to π_{t+1}, incurring a moving cost equal to the Kendall tau distance of π_t to π_{t+1}. The objective is to minimize the total access and moving cost for serving the entire sequence. We consider the runiform version, where each S_t has cardinality r. List update is the special case where r = 1.
We obtain tight bounds on the competitive ratio of deterministic online algorithms for MSSC against a static adversary, that serves the entire sequence by a single permutation. First, we show a lower bound of (r+1)(1r/(n+1)) on the competitive ratio. Then, we consider several natural generalizations of successful list update algorithms and show that they fail to achieve any interesting competitive guarantee. On the positive side, we obtain a O(r)competitive deterministic algorithm using ideas from online learning and the multiplicative weight updates (MWU) algorithm.
Furthermore, we consider efficient algorithms. We propose a memoryless online algorithm, called MoveAllEqually, which is inspired by the Double Coverage algorithm for the kserver problem. We show that its competitive ratio is Ω(r²) and 2^{O(√{log n ⋅ log r})}, and conjecture that it is f(r)competitive. We also compare MoveAllEqually against the dynamic optimal solution and obtain (almost) tight bounds by showing that it is Ω(r √n) and O(r^{3/2} √n)competitive.
BibTeX  Entry
@InProceedings{fotakis_et_al:LIPIcs:2020:12458,
author = {Dimitris Fotakis and Loukas Kavouras and Grigorios Koumoutsos and Stratis Skoulakis and Manolis Vardas},
title = {{The Online MinSum Set Cover Problem}},
booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
pages = {51:151:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771382},
ISSN = {18688969},
year = {2020},
volume = {168},
editor = {Artur Czumaj and Anuj Dawar and Emanuela Merelli},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12458},
URN = {urn:nbn:de:0030drops124582},
doi = {10.4230/LIPIcs.ICALP.2020.51},
annote = {Keywords: Online Algorithms, Competitive Analysis, MinSum Set Cover}
}
29.06.2020
Keywords: 

Online Algorithms, Competitive Analysis, MinSum Set Cover 
Seminar: 

47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Issue date: 

2020 
Date of publication: 

29.06.2020 