2026-07-23T17:31:15Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14134 2024-03-06T10:53:33Z ddc:004 open_access

On the Approximability of Multistage Min-Sum Set Cover Fotakis, Dimitris Kostopanagiotis, Panagiotis Nakos, Vasileios Piliouras, Georgios Skoulakis, Stratis Approximation Algorithms Multistage Min-Sum Set Cover Multistage Optimization Problems We investigate the polynomial-time approximability of the multistage version of Min-Sum Set Cover (Mult-MSSC), a natural and intriguing generalization of the classical List Update problem. In Mult-MSSC, 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 π^{t-1} to π^{t}, quantified by the Kendall tau distance d_{KT}(π^{t-1}, π^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 Mult-MSSC does not admit an O(1)-approximation, unless P = NP, and that any o(log n) (resp. o(r)) approximation to Mult-MSSC 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 Mult-MSSC can be approximated in polynomial-time 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Dimitris Fotakis and Panagiotis Kostopanagiotis and Vasileios Nakos and Georgios Piliouras and Stratis Skoulakis 2021 Is Part Of LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2021.65 urn:nbn:de:0030-drops-141341 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.65 eng https://creativecommons.org/licenses/by/4.0/legalcode