Fotakis, Dimitris ;
Kostopanagiotis, Panagiotis ;
Nakos, Vasileios ;
Piliouras, Georgios ;
Skoulakis, Stratis
On the Approximability of Multistage MinSum Set Cover
Abstract
We investigate the polynomialtime approximability of the multistage version of MinSum Set Cover (MultMSSC), a natural and intriguing generalization of the classical List Update problem. In MultMSSC, we maintain a sequence of permutations (π⁰, π¹, …, π^T) on n elements, based on a sequence of requests ℛ = (R¹, …, R^T). We aim to minimize the total cost of updating π^{t1} to π^{t}, quantified by the Kendall tau distance d_{KT}(π^{t1}, π^t), plus the total cost of covering each request R^t with the current permutation π^t, quantified by the position of the first element of R^t in π^t.
Using a reduction from Set Cover, we show that MultMSSC does not admit an O(1)approximation, unless P = NP, and that any o(log n) (resp. o(r)) approximation to MultMSSC implies a sublogarithmic (resp. o(r)) approximation to Set Cover (resp. where each element appears at most r times). Our main technical contribution is to show that MultMSSC can be approximated in polynomialtime within a factor of O(log² n) in general instances, by randomized rounding, and within a factor of O(r²), if all requests have cardinality at most r, by deterministic rounding.
BibTeX  Entry
@InProceedings{fotakis_et_al:LIPIcs.ICALP.2021.65,
author = {Fotakis, Dimitris and Kostopanagiotis, Panagiotis and Nakos, Vasileios and Piliouras, Georgios and Skoulakis, Stratis},
title = {{On the Approximability of Multistage MinSum Set Cover}},
booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
pages = {65:165:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771955},
ISSN = {18688969},
year = {2021},
volume = {198},
editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14134},
URN = {urn:nbn:de:0030drops141341},
doi = {10.4230/LIPIcs.ICALP.2021.65},
annote = {Keywords: Approximation Algorithms, Multistage MinSum Set Cover, Multistage Optimization Problems}
}
02.07.2021
Keywords: 

Approximation Algorithms, Multistage MinSum Set Cover, Multistage Optimization Problems 
Seminar: 

48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Issue date: 

2021 
Date of publication: 

02.07.2021 