2021/07/28 by Dimitris Fotakis, Panagiotis Kostopanagiotis, Fotakis, Dimitris +7 · 1 citation
Mathematics · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Mathematical Approximation and Integration
paper · pdf · doi:10.48550/arxiv.2107.13344
openalex publication_date 2021/07/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We investigate the polynomial-time approximability of the multistage version of Min-Sum Set Cover (DSSC), a natural and intriguing generalization of the classical List Update problem. In DSSC, we maintain a sequence of permutations (π0, π1, …, πT) on n elements, based on a sequence of requests (R1, …, RT). We aim to minimize the total cost of updating πt-1 to πt, quantified by the Kendall tau distance DKT(πt-1, πt), plus the total cost of covering each request Rt with the current permutation πt, quantified by the position of the first element of Rt in πt. Using a reduction from Set Cover, we show that DSSC does not admit an O(1)-approximation, unless P = NP, and that any o(log n) (resp. o(r)) approximation to DSSC 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 DSSC can be approximated in polynomial-time within a factor of O(log2 n) in general instances, by randomized rounding, and within a factor of O(r2), if all requests have cardinality at most r, by deterministic rounding.