Computer Science
Computer Science-2021.gz:143268
Computer Science Mathematics
38c872be89a40817b665f78a2d0dcfa288e19456
On the Approximability of Multistage Min-Sum Set Cover

We investigate the polynomial-time approximability of the multistage version of Min-Sum Set Cover ($\mathrm{DSSC}$), a natural and intriguing generalization of the classical List Update problem. In $\mathrm{DSSC}$, we maintain a sequence of permutations $(\pi^0, \pi^1, \ldots, \pi^T)$ on $n$ elements, based on a sequence of requests $(R^1, \ldots, R^T)$. We aim to minimize the total cost of updating $\pi^{t-1}$ to $\pi^{t}$, quantified by the Kendall tau distance $\mathrm{D}_{\mathrm{KT}}(\pi^{t-1}, \pi^t)$, plus the total cost of covering each request $R^t$ with the current permutation $\pi^t$, quantified by the position of the first element of $R^t$ in $\pi^t$. Using a reduction from Set Cover, we show that $\mathrm{DSSC}$ does not admit an $O(1)$-approximation, unless $\mathrm{P} = \mathrm{NP}$, and that any $o(\log n)$ (resp. $o(r)$) approximation to $\mathrm{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 $\mathrm{DSSC}$ can be approximated in polynomial-time within a factor of $O(\log^2 n)$ in general instances, by randomized rounding, and within a factor of $O(r^2)$, if all requests have cardinality at most $r$, by deterministic rounding.


Introduction
In Multistage Min-Sum Set Cover (Mult-MSSC), we are given a universe U on n elements, a sequence of requests R = (R 1 , . . . , R T ), with R t ⊆ U , and an initial permutation π 0 of the elements of U . We aim to maintain a sequence of permutations (π 0 , π 1 , . . . , π T ) of U , so as to minimize the total cost of updating (or moving from) π t−1 to π t in each time step plus the total cost of covering each request R t with the current permutation π t . The cost of moving from π t−1 to π t is the number of inverted element pairs between π t−1 and π t , i.e., the Kendall Tau distance d KT (π t−1 , π t ). The cost π t (R t ) of covering a request R t with a permutation π t is the position of the first element of R t in π t , i.e., π t (R t ) = min{i | π t (i) ∈ R t }. Thus, given R = (R 1 , . . . , R T ), we aim to minimize T t=1 d KT (π t−1 , π t ) + π t (R t ) . The Mult-MSSC problem is a natural generalization of the (offline version of the) classical List Update problem [26], where |R t | = 1 for all requests R t ∈ R. The offline version of List Update is NP-hard [2], while it is known that any 5/4-approximation has to resort to paid exchanges, where an element different from the requested one is moved forward to the list [24,28]. Mult-MSSC was introduced in [17] as the multistage extension of Min-Sum Set Cover (MSSC) [15], where we aim to compute a single static permutation π that minimizes the total covering cost T t=1 π(R t ). [17] presented a (simple polynomial-time) online algorithm for Mult-MSSC with competitive ratio between Ω(r √ n) and O(r 3/2 √ n) for r-bounded instances, where all requests have cardinality at most r, and posed the polynomial-time approximability of Mult-MSSC as an interesting open question. Mult-MSSC is also related to recently studied time-evolving (a.k.a. multistage or dynamic) optimization problems (e.g., multistage matroid, spanning set and perfect matching maintenance [19], time-evolving Facility Location [14,3]), where we aim to maintain a sequence of near-optimal feasible solutions to a combinatorial optimization problem, in response to time-evolving underlying costs, without changing too much the solution from one step to the next.

Motivation.
Mult-MSSC is motivated by applications, such as web search, news, online shopping, paper bidding, etc., where items are presented to the users sequentially. Then, the item ranking is of paramount importance, because user attention is usually restricted to the first few items in the sequence (see e.g., [27,13,16,10]). If a user does not spot an item fitting her interests there, she either leaves the service (in case of news or online shopping, see e.g., the empirical evidence in [12]) or settles on a suboptimal action (in case of paper bidding, see e.g., [11]). To mitigate such situations and increase user retention, modern online services highly optimize item rankings based on user scrolling and click patterns. Each user t is represented by her set of preferred items (or item categories) R t . The goal of the service provider is to continually maintain an item ranking π t , so that the current user t finds one of her favorite items at a relatively high position in π t . Continual ranking update is dictated by the fact that users with different characteristics and preferences tend to use the online service during the course of the day (e.g., elderly people in the morning, middle-aged people in the evening, young people at the night -similar patterns apply for people from different countries and timezones). Moreover, different user categories react in nonuniform ways to different trends (in e.g., news, fashion, sports, scientific topics). For consistency and stability, however, the ranking should change neither too much nor too frequently. Mult-MSSC makes the (somewhat simplifying) assumptions that the service provider has a relatively accurate knowledge of user preferences and their arrival order, and that its total cost is proportional to how deep in π t the current user t should reach, before she finds one of her favorite items, and to how much the ranking changes from one user to the next.
From a theoretical viewpoint, Mult-MSSC was used in [17] as a natural benchmark for studying the dynamic competitive ratio of Online Min-Sum Set Cover, where the algorithm updates its permutation online, without any knowledge of future requests. As in Mult-MSSC, the objective is to minimize the total moving plus the total covering cost.

Contribution and Techniques.
In this work, we initiate a study of the polynomial-time approximability of Mult-MSSC. Using a reduction from Set Cover, we show (Theorem 7) that Mult-MSSC does not admit a c log n-approximation, for some absolute constant c, unless P = NP. Moreover our reduction establishes that an o(r)-approximation for r-bounded instances of Mult-MSSC implies an o(r)-approximation for Set Cover, in case each element appears in at most r requests.
Our main technical contribution is to show that Mult-MSSC can be approximated in polynomial-time within a factor of O(log 2 n) in general instances, by randomized rounding (Theorem 10), and within a factor of O(r 2 ) in r-bounded instances, by deterministic rounding (Theorem 11).
For both results, we consider a restricted version of Mult-MSSC, inspired by the Move-to-Front (MTF) algorithm for List Update, where in each time step t, we can only move a single element of R t from its position in π t−1 to the first position of π t . Since such a permutation π t coves R t with unit cost, we now aim to select the element of each R t moved to front of π t , so as to minimize the total moving cost T t=1 d KT (π t−1 , π t ). It is not hard to see that the optimal cost of serving R under the restricted Move-to-Front version of Mult-MSSC is within a factor of 4 from the optimal cost under the original, more general, definition of Mult-MSSC.
Hence, approximating Mult-MSSC boils down to determining which element of R t should become the top element of π t . To this end, we relax permutations to doubly stochastic matrices and consider a Linear Programming relaxation of the restricted Move-to-Front version of Mult-MSSC, which we call Fractional-MTF (see Definition 8). Given the optimal solution of the aforementioned linear program, which is a sequence of doubly stochastic matrices (A 0 , A 1 , . . . , A T ), with A 0 corresponding to the initial permutation π 0 , our main technical challenge is to round each doubly stochastic matrix A t to a permutation π t such that (i) there is an element of R t at one of the few top positions of π t ; and (ii) the total moving cost T t=1 d KT (π t−1 , π t ) of the rounded solution is comparable to the total moving cost T t=1 d FR (A t−1 , A t ) of the optimal solution of Fractional-MTF, where d FR is a notion of distance equivalent to Spearman's footrule distance on permutations (see Definition 4).
Working towards a randomized rounding approach, we first observe that rounding each doubly stochastic matrix independently may result in a permutation sequence with total moving cost significantly larger than that of Fractional-MTF (see also the discussion after Lemma 9). In Theorem 10, we show that a dependent randomized rounding with logarithmic scaling of entries (Algorithm 1), similar in spirit with the randomized rounding approach [8,25] for Generalized Min-Sum Set Cover, results in an approximation ratio of O(log 2 n). Interestingly, Algorithm 1 without the logarithmic scaling results in a permutation sequence with the expected moving cost within a factor of 4 from the optimal moving cost of Fractional-MTF. However, we lose a logarithmic factor in the approximation ratio, because we need to scale up the entries of each doubly stochastic matrix A t , so as to ensure that some element of R t appears in the few top positions of π t with sufficiently large probability. The other logarithmic factor is lost because there could be a logarithmic number of elements allocated to the same position of the resulting permutation by the randomized rounding. Our deterministic rounding of Algorithm 2 for r-bounded request sequences is motivated by the deterministic rounding for Set Cover and Vertex Cover. We observe that in the optimal solution of Fractional-MTF, in each time step t, there is some element e ∈ R t with A t e1 ≥ 1/r (i.e., e occupies a fraction of at least 1/r of the first position in the "fractional permutation" A t ). Algorithm 2 simply moves any such element to the front of π t . The most challenging part of the analysis is to establish that for any optimal solution (A 0 , A 1 , . . . , A T ) of Fractional-MTF with respect to an r-bounded request sequence, there exists a sequence of doubly stochastic matrices (A 0 ,Â 1 , . . . ,Â T ) with the entries of eachÂ t being multiples of 1/r, such that (i) the moving cost of (A 0 ,Â 1 , . . . ,Â T ) is bounded from above by the optimal cost of Fractional-MTF; and (ii) each matrixÂ t contains in the first position the element that Algorithm 2 keeps in the first position at round t, with mass at least 1/r. Then we show (Lemma 20) that for any sequence of doubly stochastic matrices (A 0 ,Â 1 , . . . ,Â T ) satisfying the above properties, the moving cost of Algorithm 2 is at most the moving cost of the doubly stochastic matrices, . The latter is done through the use of an appropriate potential function based on an extension of the Kendall-Tau distance to doubly stochastic matrix with entries being multiples of 1/r.
A potentially interesting insight is that the technical reason for the quadratic dependence of our approximation ratios on log n and r is conceptually similar to the reason for the (best possible) approximation ratio of 4 = 2 · 2 in [15] (see the discussion after Theorem 10). Hence, we conjecture that any o(log 2 n) (resp. o(r 2 )) approximation to Mult-MSSC must imply a sublogarithmic (resp. o(r)) approximation to Set Cover.
Other Related Work. The MSSC problem generalizes various NP-hard problems, such as Min-Sum Vertex Cover and Min-Sum Coloring and it is well-studied. Feige, Lovasz and Tetali [15] proved that the greedy algorithm, which picks in each position the element that covers the most uncovered requests, is a 4-approximation (that was also implicit in [9]) and that no (4 − ε)-approximation is possible, unless P = NP. In Generalized MSSC (a.k.a. Multiple Intents Re-ranking), there is a covering requirement K(R t ) for each request R t and the cost of covering a request R t is the position of the K(R t )-th element of R t in the (static) permutation π. The MSSC problem is the special case where K(R t ) = 1 for all requests R t . Another notable special case of Generalized MSSC is the Min-Latency Set Cover problem [20], which corresponds to the other extreme case where K(R t ) = |R t | for all requests R t . Generalized MSSC was first studied by Azar et al. [5], who presented a O(log r)-approximation; later O(1)-approximation algorithms were obtained [8,25,23,6].
Further generalizations of Generalized MSSC have been considered, such as the Submodular Ranking problem, studied in [4], which generalizes both Set Cover and MSSC, and the Min-Latency Submodular Cover, studied by Im et al. [22]. We refer to [22,21] for a detailed discussion on the connections between these problems and their applications.
The online version of MSSC, which generalizes the famous List Update problem, was studied in [17]. They proved that its static deterministic competitive ratio is Θ(r) and presented a natural memoryless algorithm, called Move-all-Equally, with static competitive ratio in Ω(r 2 ) and 2 O( √ log n·log r) and dynamic competitive ratio in Ω(r √ n) and O(r 3/2 √ n)competitive. Subsequently, [18] considered MSSC from the viewpoint of online learning. Through dimensionality reduction from permutations to doubly stochastic matrices, they obtained randomized (resp. deterministic) polynomial-time online learning algorithms with O(1)-regret for Generalized MSSC (resp. O(r)-regret for MSSC).

Preliminaries and Basic Definitions
The set of elements e is denoted by U with |U | = n. A permutation of the elements is denoted by π where π i denotes the element lying at position i (for 1 ≤ i ≤ n) and Pos(e, π) denotes the position of the element e ∈ U in permutation π.
The Kendall-Tau distance and FootRule distance are approximately equivalent, . Moreover both of them satisfy the triangle inequality. The notion of FootRule distance can be naturally extended to stochastic matrices. Given two doubly stochastic matrices A, B consider the min-cost transportation problem, transforming row A e to the row B e where the cost of transporting a unit of mass between column i and column j equals |i − j|. Formally for each row e, define a complete bipartite graph where on the left part lie the entries (e, i) for 1 ≤ i ≤ n and on the right part the entries (e, j) for 1 ≤ j ≤ n. The mass transported from entry (e, i) to entry (e, j) (denoted as f e ij ) costs f e ij · |i − j| and the total mass leaving (e, i) equals A ei and the total mass arriving at (e, j) equals B ej .
Up next we present the formal definition of Multistage Min-Sum Set Cover.
▶ Definition 6 (Multistage Min-Sum Set Cover). Given a universe of elements U , a sequence of requests R 1 , . . . , R T ⊆ U and an initial permutation of the elements π 0 . The goal I C A L P 2 0 2 1 108:6 On the Approximability of Multistage Min-Sum Set Cover is to select a sequence of permutation π 1 , . . . , π T that minimizes We refer to T t=1 π t (R t ) as covering cost and to T t=1 d KT (π t , π t−1 ) as moving cost. We denote with π t Opt the permutation of the optimal solution of Mult-MSSC at round t, with o t the element that the optimal solution uses to cover the request R t (the element of R t appearing first in π t Opt ), and with OPT Mult-MSSC the cost of the optimal solution. Finally we call an instance of Mult-MSSC r-bounded in case the cardinality of the requests is bounded by r, |R t | ≤ r.

Approximation Algorithms for Multistage Min-Sum Set Cover
There exists an approximation-preserving reduction from Set − Cover to Mult-MSSC that provides us with the following inapproximability results.

▶ Theorem 7.
There is no c · log n-approximation algorithm for Mult-MSSC (for a sufficienly small constant c) unless P = NP. Let a c-approximation algorithm for Mult-MSSC producing the permutation π 1 , . . . , π m the cost of which is denoted by Alg. Let also CoverAlg denote the set composed by the element that the c-approximation algorithm uses to cover the requests, CoverAlg = {the element of S t appearing first in π t }. Then, Now consider the following solution for Mult-MSSC constructed by the optimal solution for Set − Cover. This solution initially moves the elements of the optimal covering set OPT SetCover to the first positions and then never changes the permutation. Clearly the cost of this solution is upper bounded by There is no polynomial-time approximation algorithm for Set−Cover with approximation ratio better than log m. The latter holds even for instance of Set − Cover for which m = poly(n) [1] where poly(·) is a polynomial with degree bounded by a universal constant. Since the number of elements |U |, in the constructed instance of Mult-MSSC is n 2 m, any c · log |U |approximation for Mult-MSSC (for c sufficiently small) implies an approximation algorithm for Set − Cover with approximation ratio less than log n. In case there exists an c = o(r)approximation algorithm for Mult-MSSC for requests sequences R 1 , . . . , R T where |R t | ≤ r, we obtain an o(r)-approximation for algorithm for Set − Cover for sets with cardinality bounded by r. In the standard form of Set − Cover this is translated into the fact that each element belongs in at most r sets. ◀ Both the O(log 2 n)-approximation algorithm (for requests of general cardinality) and the O(r 2 )-approximation algorithm for r-bounded requests, that we subsequently present, are based on rounding a linear program called Fractional Move To Front. The latter is the linear program relaxation of Move To Front, a problem closely related to Multistage Min-Sum Set Cover. MTF asks for a sequence of permutations π 1 , . . . , π T such as at each round t, an element of R t lies on the first position of π t and T t=1 d FR (π t , π t−1 ) is minimized.
▶ Definition 8. Given a sequence of requests R 1 , . . . , R T ⊆ U and an initial permutation of the elements π 0 , consider the following linear program, called Fractional − MTF, There is an elegant argument (appeared in previous works, e.g., [17]) showing that the optimal solution of MTF is at most 4 · OPT Mult-MSSC . In Lemma 9 we provide the argument and establish that Fractional − MoveToFront is a 4-approximate relaxation of Mult-MSSC.
Proof of Lemma 9. Let o t the element of R t appearing first in the permutation π t Opt . Consider the sequence of permutation π 0 , π 1 , . . . , π T constructed by moving at each round I C A L P 2 0 2 1 108:8 On the Approximability of Multistage Min-Sum Set Cover t, the element o t to the first position of the permutation. Notice that π 0 , π 1 , . . . , π T is a feasible solution for both MoveToFront and Fractional − MTF. The first key step towards the proof of Lemma 9 is that To understand the above inequality, let k t be the position of o t in permutation π t−1 . Out of the Opt ) and the previous inequality we get, and by a telescopic sum we get The proof follows by the fact that d FR (π t , π t−1 ) ≤ 2 · d KT (π t , π t−1 ). ◀ As already mentioned, our main technical contribution is the design of rounding schemes converting the optimal solution, A 1 , . . . , A T , of Fractional − MTF into a sequence of permutations π 1 , . . . , π T . This is done so as to bound the moving cost of our algorithms by the moving cost T t=1 d FR (A t , A t−1 ). We then separately bound the covering cost, T t=1 π t (R t ) by showing that always an element of R t lies on the first positions of π t .
The main technical challenge in the design of our rounding schemes is ensure to that the moving cost of our solutions . Despite the fact that the connection between doubly stochastic matrices and permutations is quite well-studied and there are various rounding schemes converting doubly stochastic matrices to probability distributions on permutations (such as the Birkhoff-von Neumann decomposition or the schemes of [8,25,6,17]), using such schemes in a black-box manner does not provide any kind of positive results for Mult-MSSC. For example consider the case where A 1 = · · · = A T and thus In case a randomized rounding scheme is applied independently to each A t , there always exists a positive probability that π t ̸ = π t−1 and thus the moving cost will far exceed d FR (A 1 , A 0 ) as T grows. The latter reveals the need for coupled rounding schemes that convert the overall sequence of matrices A 1 , . . . , A T to a sequence of permutations π 1 , . . . , π T . Such a rounding scheme is presented in Algorithm 1 and constitutes the back-bone of our approximation algorithm for requests of general cardinality.
The rounding scheme described in Algorithm 1, imposes correlation between the different time-steps by simply requiring that each element e selects α e once and for all and by breaking ties lexicographically (any consistent tie-breaking rule would also work). In Lemma 12 of Section 4, we show that no matter the sequence of doubly stochastic matrices, the rounding scheme of Algorithm 1 produces a sequence of permutations with overall moving cost at most 4 log 2 n the moving cost of the matrix-sequence 1 and thus establishes that the overall moving cost of Algorithm 1 is bounded by 4 log 2 n · OPT Mult-MSSC . The log n multiplication in Step 7 serves as a probability amplifier ensuring that at least one element of R t lies in the relatively first positions of π t and permits us to approximately bound the covering cost
1: Find the optimal solution A 0 = π 0 , A 1 , . . . , A T for Fractional − MTF. 2: for each element e ∈ U do 3: Select α e uniformly at random in [0, 1]. 4: end for 5: for t = 1 . . . T do 6: for all elements e ∈ U do 7: Despite the fact that in Step 7 of Algorithm 1, we multiply the entries of A t with log n the overall guarantee is O(log 2 n). At a first glance the latter seems quite strange but admits a rather natural explanation. For most of the positions i, the probability that an element e admits index I t e = i is roughly log n · A t ei , but due to the fact each index j ≤ i is on expectation selected by log n other elements, the expected position of e in the produced permutation is roughly log 2 n times the expected value of argmin 1≤i≤n { i s=1 A t es ≥ α e }. This phenomenon relates with the elegant fitting argument given in [15] to prove that the greedy algorithm is 4-approximation for the original Min-Sum Set Cover (which is tight unless P = NP). The latter makes us conjecture that the tight inapproximability bound for Mult-MSSC is Ω(log 2 n) for requests of general cardinality.
Motivated by the r-approximation LP-based algorithm for instances of Set − Cover in which elements belong in at most r sets, we examine whether the O(log 2 n) for Mult-MSSC can be ameliorated in case of r-bounded request sequences. Interestingly, the simple greedy rounding scheme (described 2 in Algorithm 2) provides such a O(r 2 )-approximation algorithm.

Algorithm 2 A Greedy-Rounding Algorithm for Mult-MSSC for r-Bounded Sequences.
Input: A request sequence R 1 , . . . , R T with |R t | ≤ r and an initial permutation π 0 . Output: A sequence of permutations π 1 , . . . , π T . 1: Find the optimal solution A 0 = π 0 , A 1 , . . . , A T for Fractional − MTF. 2: for t = 1 . . . T do 3: π t := in π t−1 , move to the first position an element e ∈ R t such that A t e1 ≥ 1/r 4: end for The O(r 2 )-approximation guarantee of Algorithm 3 is formally stated and proven in Theorem 11. The main technical challenge is that we cannot directly compare the moving cost of Algorithm 2 with T t=1 d FR (A t , A t−1 ) and thus we deploy a two-step detour. 2 Step 3 of Algorithm 2 is well-defined since |Rt| ≤ r and e∈Rt A t e1 = 1.
In the first step (Lemma 19), we prove the existence of a sequence of doubly stochastic matricesÂ 0 = π 0 ,Â 1 , . . . ,Â T for which eachÂ t satisfies that (i) its entries of are multiples of 1/r, (ii)Â t et1 ≥ 1/r where e t is the element that Algorithm 2 moves to the first position at round t, and (iii) the sequenceÂ 0 = π 0 ,Â 1 , . . . ,Â T admits moving cost at most T t=1 d FR (A t , A t−1 ). In order to establish the existence of such a sequence, we construct an appropriate linear program (see Definition 18) based on the elements that Algorithm 2 moves to the first position at each round and prove that it admits an optimal solution with values being multiples of 1/r. To do the latter, we relate the linear program of Definition 18 with a fractional version of the k-Paging [7] problem and based on the optimal eviction policy (evict the page appearing the furthest in the future), we design an algorithm producing optimal solutions for the LP with values being multiple of 1/r.
In the second step (Lemma 20), we show that for any sequenceÂ 0 = π 0 ,Â 1 , . . . ,Â T satisfying properties (i) and (ii), the moving cost of Algorithm 2 is at most O(r 2 ) · T t=1 d FR (Â t ,Â t−1 ). The latter is achieved through the use of an appropriate potential function based on a generalization of Kendall-Tau distance to doubly stochastic matrices with entries being multiples of 1/r (see Definition 23).

▶ Theorem 11. Algorithm 2 is a O(r 2 )-approximation algorithm for Mult-MSSC.
In Section 4 and 5 we provide the basic steps and ideas in the proof of Theorem 10 and 11 respectively.

Proof of Theorem 10
The basic step towards the proof of Theorem 10 is Lemma 12, establishing the fact that once two doubly stochastic matrices are given as input to the randomized rounding of Algorithm 1, the expected distance of the produced permutations is approximately bounded by the distance of the respective doubly stochastic matrices.
▶ Lemma 12. Let the doubly stochastic matrices A, B given as input to the rounding scheme of Algorithm 1. Then for the produced permutations π A , π B , E d KT (π A , π B ) ≤ 4 log 2 n · d FR (A, B).
Before exhibiting the proof of Lemma 12 we introduce the notion of neighboring matrices.  (A, B). Proof Sketch of Claim 15. Let f e ij denotes the optimal solution of the linear program of Definition 4 defining the FootRule distance d FR (A, B). In case A ̸ = B, there exist elements e 1 , e 2 and indices i < j such that f e1 iℓ(i) > 0 and f e2 jℓ(j) > 0 with ℓ(i) >= j and ℓ(j) <= i.

the column-sum is bounded by 2, e∈U
Let ϵ = min(f e1 iℓ(i) , f e2 jℓ(j) ) and consider the sequence of the |i−j| matrices produced by moving ϵ amount of mass in row e 1 from column i to column j. Then consider the sequence of the |i−j| matrices produced by moving ϵ amount of mass in the row e 2 from column j to column i.
In the overall sequence of 2|i−j| stochastic matrices, two consecutive matrices are neighboring. Furthermore the column-sum of the matrices does not exceed 1 + ϵ ≤ 2 and the final matrix A ′ of the sequence is doubly stochastic. Moreover by the fact that t(i) ≥ j and t(j) ≤ i we get that the overall moving cost of the sequence equals d The notion of neighboring matrices is rather helpful since Lemma 12 admits a fairly simple proof in case A, B are neighboring stochastic matrices (notice that the rounding scheme of Algorithm 1 is well-defined even for stochastic matrices). The latter is formally stated and proven in Lemma 17 and is the main technical claim of the section.
I C A L P 2 0 2 1

108:12 On the Approximability of Multistage Min-Sum Set Cover
Notice also that in case I A e ⋆ = I B e ⋆ , d KT (π A , π B ) = 0. This is due to the fact that in such a case I A e = I B e for all e ∈ U and the fact that ties are broken lexicographically. As a result, where the last inequality follows by the fact that once I A e * = i * and I B e * = i * + 1, the element e * can move at most by |O i * | + |O i * +1 | positions and the fact that I A e * , I B e * and |O i * |, |O i * +1 | are independent random variables.
We complete the proof we providing a bound on E [|O i |]. Notice that for e ∈ U/{e * }, The proof of Lemma 12 easily follows by Claim 15 and Lemma 17. A 0 , A 1 , . . . , A T = B of neighboring stochastic matrices ensured by Claim 15. Now let π 0 , π 1 , . . . , π T the sequence of permutations that the randomized rounding of Algorithm 1 produces given as input the sequence A = A 0 , A 1 , . . . , A T = B. Notice that,

Proof of Lemma 12. Given the doubly stochastic matrices A, B, let the sequence A =
where the first inequality follows by the triangle inequality, the second by Lemma 17 and the last equality by Case 4 of Claim 15. ◀ We conclude the section with the proof of Theorem 10.
Proof of Theorem 10. By Lemma 12 and Lemma 9, . Notice that since e∈Rt A t e1 = 1, the only elements that can have index I t e = 1 are the elements e ∈ R t . As a result, in case there exists some e at round t with I t e = 1 then π t (R t ) = 1.
where the last inequality follows due to the fact that e∈Rt A t e1 = 1 and π t Opt (R t ) ≥ 1. ◀

Proof of Theorem 11
In this section we present the basic steps towards the proof of Theorem 11. We remind that |R t | ≤ r and we denote with e t the element that Algorithm 2 moves in the fist position at round t. As already mentioned, the proof is structured in two different steps.

1.
We prove the existence of a sequence of doubly stochastic matricesÂ 0 = π 0 ,Â 1 , . . . ,Â T such that (i) the entries of eachÂ t are multiples of 1/r, (ii) eachÂ t admits 1/r mass for element e t in first position (Â t et1 ≥ 1/r) and (iii) We use properties (i) and (ii) to prove that the moving cost of Algorithm 2 is roughly upper bounded by Θ( We start with the construction of the sequenceÂ 0 = π 0 ,Â 1 , . . . ,Â T . ▶ Lemma 19. There exists an optimal solutionÂ = π 0 ,Â 1 , . . . ,Â T for the linear program of Definition 19 such that entries of eachÂ t are multiples of 1/r. The proof of Lemma 19 is one of the main technical contributions of this work. Due to lack of space its proof is deferred to the full version of the paper. We remark that the semi-integrality property, that Lemma 19 states, is not due to the properties of the LP's polytope and in fact there are simple instances in which the optimal extreme points do not satisfy it. We establish Lemma 19 via the design of an optimal algorithm for the LP of Definition 18 (Algorithm 3) that always produces solutions with entries being multiples of 1/r. Up next we describe in brief the idea behind Algorithm 3. Given the matrixÂ t−1 , Algorithm 3 constructÂ t as follows. At first it moves 1/r mass from the left-most entry (e t , j) withÂ t−1 etj ≥ 1/r to the entry (e t , 1). At this point the third constraint of the LP in Definition 18 is satisfied but the column-stochasticity constraints are violated (the first column admits mass 1 + 1/r and the j-th column admits mass 1 − 1/r). Algorithm 3 inductively restores column-stochasticity from left to right. At step i, all the columns on the left of i are restored and the violations concern the column i and j (i's mass is 1 + 1/r and j's mass is 1 − 1/r). Now Algorithm 3 must move a total of 1/r mass from column i to column i + 1. In case there exists an element e with total amount of mass greater than 2/r, Algorithm 2 moves the 1/r mass from the entry (e, i) to the entry (e, i + 1). The reason is that even if e = e t ′ at some future round t ′ , the third constraint only requires 1/r mass. In case there is no such element, Algorithm 3 moves the 1/r mass from the element appearing the furthest in the sequence {e t , . . . , e T }. The latter is in accordance with the optimal eviction policy for k − Paging which at each round evicts the page appearing furthest in the future [7]. The optimality of Algorithm 3 is established in Lemma 21 and the fact that produced solution admits values being 1/r is inductively established.
To this end, we can show that all of the desired properties of the sequenceÂ = π 0 ,Â 1 , . . . ,Â T are satisfied. Property (i) is established by Lemma 19. Property (ii) is enforced by the constraintÂ t et1 ≥ 1/r. Now for Property (iii), notice that by the definition of Algorithm 2, A t et1 ≥ 1/r. As a result, the sequence A 0 = π 0 , A 1 , . . . , A T is feasible for the linear program of Definition 18 and thus ▶ Lemma 20. Let π 0 , π 1 , . . . , π T the permutations produced by Algorithm 2 and e 1 , . . . , e T the elements that Algorithm 2 moves to the first position at each round t. For any sequence of doubly stochastic matricesÂ 0 = π 0 ,Â 1 , . . . ,Â T for which Property (i) and Property (ii) are satisfied, The proof of Theorem 11 directly follows by Lemma 19 and 20. In Section 5.2 we present the basic steps for of Lemma 19.

Proof of Lemma 19
We prove the existence of an optimal solutionÂ 0 = π 0 ,Â 1 , . . . ,Â T for the linear program of Definition 18 for which the entries of each matrixÂ t are multiples of 1/r though the design of an optimal greedy algorithm illustrated in Algorithm 3.
The fact that Algorithm 3 produces a solution with entries that multiples of 1/r easily follows. Algorithm 3 starts with an integral doubly stochastic matrices (Â 0 = π 0 ) and always moves 1/r mass from entry to entry. The optimality of Algorithm 3 is established in Lemma 21 the proof of which is presented in the next section since it is quite technically complicated. However the basic idea of the algorithms is very intuitive, onceÂ t−1 et = 0 Algorithm 3 moves 1/r mass of e t from its leftmost position (with mass greaer than 1/r), denoted as Pos of Step 5. At this point of time, Algorithm 3 has violated the column-stochasticity constraints, 1 + 1/r for the first column and 1 − 1/r for the Pos-th column and Algorithm 3 must move at total of 1/r mass from the first position to next positions until 1/r mass reaches the Pos position and column-stochasticity is restored (Step 8). Once Algorithm 3 detects an element with aggregated mass (until position j) ≥ 2/r, it can safely move 1/r of each mass to position j + 1 since even if this element appears at some point in the future only 1/r is necessary to satisfy the constraint A t et1 ≥ 1/r and thus the rest is redundant (Step 11). In case such an element does not exist, Algorithm 3 moves the (useful) 1/r mass of the element appearing the furthest in the remaining sequence {e t , . . . , e T }, which is exactly the same optimal eviction policy that the well-studied k − Paging suggests.

Proof of Lemma 20
In order to prove Lemma 20, we make use of an appropriate potential function that can be viewed as an extension of the Kendall-Tau distance (see Definition 1) to doubly stochastic matrices with entries being multiples of 1/r.

Algorithm 3 An Optimal Greedy Algorithm for the LP of Definition 18
Input: The initial permutation π 0 and the sequence of elements e 1 , . . . , e T ∈ U Output: An optimal solution of a linear program of Definition 18 where the entries ofÂ t are multiples of 1/r.   (A, B), is the number of inverted pairs of elements.
Notice that in case of 0 − 1 doubly stochastic matrices the Fractional Kendall-Tau distance of Definition 23 coincides with the Kendall-Tau distance of Definition 1.   (A, B).
Proof of Lemma 25. We construct a doubly stochastic matrix A ′ for which the following properties hold, 1. The entries of A ′ are multiples of 1 r .
Once the above properties are established, Lemma 25 follows by repeating the same construction until matrix B is reached and by using the fact that the fractional Kendall-Tau distance of Definition 23 satisfies the triangle inequality.
Before proceeding with the construction of A ′ , we present the following corollary that follows by an easy exchange argument. In order to construct the matrix A ′ satisfying the Properties 1-3, we consider three different classes of the entries (e, i). In particular, we call an entry (e, i). We construct the matrix A ′ from matrix A as follows. Consider two entries (e, i) and (e ′ , j) with the properties that Corollary 27 illustrates. The doubly stochastic matrix A ′ is constructed by moving 1/r mass from entry (e, i) to entry (e, j) and by moving 1/r mass from entry (e ′ , j) to entry (e ′ , i). More formally, Since (e, i) is right, there exists an index ℓ(i) > i such that f e iℓ(i) > 0. Moreover f e iℓ(i) ≥ 1/r since f e iℓ(i) is multiple of 1/r. Notice that ℓ(i) ̸ = ℓ for ℓ ∈ {i + 1, j − 1} since all the entries (α, ℓ) are neutral (otherwise α∈U B αℓ > 1). As a result, transfering 1/r mass from entry (e, i) to entry (e, j) decreases the FootRule distance between A and B by 1/r · |i − j| since the final destination of the 1/r mass is the entry (e, ℓ(i)) that is on the right of entry (e, j), ℓ(i) ≥ j. The claim follows by applying the exact same argument for (e ′ , j). ◀ We now establish the last property that is d KT (A, A ′ ) ≤ 2r 2 · d FR (A, A ′ ).
▷ Claim 29. d KT (A ′ , B) ≤ 4r · |i − j| Proof. Notice that apart from e, e ′ , the r-index of each element is the same in both A and A ′ (I A α = I A ′ α for all α ∈ U \ {e, e ′ }). As a result, by Definition 23, we get that the only inverted pairs can be of the form (e, α) or (e ′ , α).
In case I A e ≤ i − 1 then I A e = I A ′ e and there is no inverted pair of the form (e, α). In case I A e = i then i ≤ I A ′ e ≤ j and any element α with I A α = I A ′ α ∈ {1, i−1}∪{j +1, n} cannot form an inverted pair with e. As a result, a pair (e, α) can be inverted only if i ≤ I A α = I A ′ α ≤ j. Since the entries of A are multiples of 1/r and A is doubly stochastic, there are at most r positive entries at each column of A. As a result, there are at most r · (j − i + 1) inverted pairs of the form (e, α). With the symmetric argument one can show that there are at most r · |j − i + 1| of the form (e ′ , α). Overall there are at most 2r · |j − i + 1| inverted pairs between A and A ′ that are less than 4r · |j − i| since j > i. Proof of Lemma 30. Since B t et ≥ 1/r, the r-index of element e t in matrix B t is 1, I B t et = 1. We first show that, d KT π t , π t−1 + d KT π t , B t − d KT π t−1 , B t ≤ r To simplify notation let k t the position of e t in π t−1 . Notice that d KT π t , π t−1 = k t − 1. Out of the k t − 1 elements lying on the left of e t in π t−1 there are most r − 1 elements α with I B t α = 1 (these elements must admit B t α1 ≥ 1/r). The rest of the k t − 1 elements admit r-index I B t α ≥ 2 and thus form inverted pairs with e t when considering π t−1 and B t .
When e t moves to the first positions (permutation π t ) these inverted pairs are deactivated (I B t et = 1) and new inverted pairs are created between e t and α with I B t α = 1, but these new inverted pairs are at most r (for any element α with I B t α , B t α ≥ 1/r). Also notice no additional inverted pairs (e, α) (with e ̸ = e t ) are created since the order between all the other elements is the same in π t and π t−1 . Overall, Combining the above inequality with d KT π t−1 , B t − d KT π t−1 , B t−1 ≤ d KT B t , B t−1 which follows from the triangle inequality we get, Finally a telescopic sum gives

Concluding Remarks
In this work we examine the polynomial-time approximability of Multistage Min-Sum Set Cover. We present Ω(log n) and Ω(r) inapproximability results for general and rbounded request sequences, while we respectively provide O(log 2 n) and O(r 2 ) polynomialtime approximation algorithms. Closing this gap is an interesting question that our work leaves open. Another interesting research direction concerns the competitive ratio in the online version of Dynamic Min-Sum Set Cover. [18] provides an Ω(r) lower bound and a Θ r 3/2 √ ncompetitive online algorithm for r-bounded sequences. Designing online algorithms for a relaxation of the problem (such as the Fractional − MTF) and using the rounding schemes that this work suggests may be a fruitful approach towards closing this gap.