Answer: Yes. A causal randomized policy, unaware of the horizon, achieves a strict expected \(O(r^2)\) competitive ratio with expected processing time polynomial in \(m,\tau_t,L_t,r\) per epoch.
Theorem 16 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThere exist a randomized O(r2)-competitive algorithm and a deterministic O(r4)-competitive algorithm for the Min-Sum Set Cover problem.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given an initial ranking \(\pi_0\) of \(n\) items and a sequence of cohorts, where cohort \(t\) has a binary-rational distribution \(\mu_t\) over request-set types \(R\subseteq U\) with \(1\le |R|\le r\) and support size \(\tau_t\), can a causal randomized policy choose one shared ranking per cohort so that its expected total cost is \(O(r^2)\) times the offline dynamic optimum? The cohort’s access cost under the current ranking \(\pi_{t-1}\) is \(\sum_R \mu_t(R)\min_{x\in R}\pi_{t-1}(x)\); after service, the policy chooses \(\pi_t\) and pays Kendall tau distance \(d(\pi_{t-1},\pi_t)\). Require the policy to run in time polynomial in \(n\), \(\tau_t\), and the mass bit length per epoch, without needing to know the horizon.
Let \(U\) contain \(m=n\ge 1\) items, let \(1\le r\le m\), and fix an initial strict ranking \(\pi_0\). Rankings assign positions \(1,\ldots,m\).
Each cohort is a society given by its support: a list of \(\tau_t\) request-set types \(R\subseteq U\), with \(1\le |R|\le r\), and positive binary-rational masses \(\mu_t(R)\) summing to \(1\). Here \(\tau_t\) is the support size, not the number of possible types; \(L_t\) is the total bit length of the cohort encoding.
At epoch \(t\), the entire distribution \(\mu_t\) is revealed. The policy pays \(a_t(\pi_{t-1})=\sum_{R\in\operatorname{supp}(\mu_t)}\mu_t(R)\min_{x\in R}\pi_{t-1}(x)\), then chooses one shared ranking \(\pi_t\) and pays Kendall tau distance \(d(\pi_{t-1},\pi_t)\). Arbitrary reordering, including no change, is allowed.
For a finite sequence \(I=(\pi_0,\mu_1,\ldots,\mu_T)\), define \(\operatorname{OPT}(I)=\min_{\sigma_0=\pi_0,\sigma_1,\ldots,\sigma_T}\sum_{t=1}^{T}[a_t(\sigma_{t-1})+d(\sigma_{t-1},\sigma_t)]\); the minimizer knows the entire sequence.
Does there exist a causal randomized policy, unaware of \(T\), with expected processing time polynomial in \(m,\tau_t,L_t,r\) per epoch, such that \(\mathbb E[\operatorname{cost}(I)]\le C r^2\operatorname{OPT}(I)\) for a universal constant \(C\) and every sequence \(I\) fixed independently of its random bits?
For point-mass cohorts, a computationally efficient randomized \(O(r^2)\)-competitive algorithm and an existential deterministic \(O(r^4)\) guarantee are known ([Bienkowski–Mucha](https://ojs.aaai.org/index.php/AAAI/article/view/25835)).
A later constructive deterministic algorithm achieves \(O(r^2)\) against the dynamic optimum ([Basiak–Bienkowski–Tatarczuk](https://arxiv.org/abs/2306.17755)). No result settling the distribution-valued cohort question was located.
Yes. Sample one request set independently from each revealed cohort and feed it to the deterministic point-request algorithm of Basiak–Bienkowski–Tatarczuk. This produces one shared ranking per epoch. The sampling reduction preserves the competitive ratio in expectation.
The proof below establishes both the strict multiplicative guarantee and the required expected polynomial processing time.
For a nonempty request set \(R\), define its access cost at ranking \(\pi\) by \(f_R(\pi)=\min_{x\in R}\pi(x)\).
We use the following published result: the deterministic algorithm DLM, initialized at \(\pi_0\), satisfies
\(\operatorname{cost}_{\mathrm{DLM}}(J)\le C_0r^2\operatorname{OPT}_{\mathrm{pt}}(J)\)
for every finite point-request sequence \(J=(\pi_0,Q_1,\ldots,Q_T)\) with \(1\le |Q_t|\le r\), for a universal constant \(C_0\). Its model charges access before reordering and Kendall distance for reordering, and the algorithm does not know the horizon. Crucially, the guarantee is strict, with no additive term. These are the model in Section 1.1 and the conclusion of Theorem 13 of [Basiak–Bienkowski–Tatarczuk](https://arxiv.org/html/2306.17755v1).
Here \(\operatorname{OPT}_{\mathrm{pt}}\) is precisely the optimum in the question specialized to point-mass cohorts.
Maintain the state of one DLM instance, initially at \(\pi_0\).
At epoch \(t\):
The DLM instance treats \(f_{Q_t}(\pi_{t-1})\) as its virtual access cost. The policy actually pays the full cohort access cost.
This policy is causal and does not use \(T\). It produces one ranking for the entire cohort.
Fix an arbitrary finite cohort sequence \(I\) independently of the policy’s random bits. Let
\(J=(\pi_0,Q_1,\ldots,Q_T)\)
be the sampled point-request sequence.
Because DLM is deterministic, \(\pi_{t-1}\) is determined by \(Q_1,\ldots,Q_{t-1}\). Conditional on these earlier samples, the fresh sample \(Q_t\) has distribution \(\mu_t\). Consequently,
\(\mathbb E[f_{Q_t}(\pi_{t-1})\mid Q_1,\ldots,Q_{t-1}]=\sum_{R\in\operatorname{supp}(\mu_t)}\mu_t(R)f_R(\pi_{t-1})=a_t(\pi_{t-1}).\)
The cohort policy and the virtual DLM execution have exactly the same ranking sequence, so their movement costs agree for every realization. Taking expectations and summing gives
\(\mathbb E[\operatorname{cost}(I)]=\mathbb E[\operatorname{cost}_{\mathrm{DLM}}(J)].\)
All these expectations are finite: each access cost is at most \(m\), and each Kendall distance is at most \(\binom m2\).
For each realization of \(J\), the point-request theorem applies, since every sampled set is nonempty and has cardinality at most \(r\). Therefore,
\(\mathbb E[\operatorname{cost}(I)]\le C_0r^2\mathbb E[\operatorname{OPT}_{\mathrm{pt}}(J)].\)
Choose an optimal cohort ranking sequence \(\sigma_0,\ldots,\sigma_T\), where \(\sigma_0=\pi_0\). Such a sequence exists because the set of feasible ranking sequences is finite.
Fix this comparator before considering the samples. For every realization of \(J\), it remains a feasible point-request comparator. Thus,
\(\operatorname{OPT}_{\mathrm{pt}}(J)\le\sum_{t=1}^T[f_{Q_t}(\sigma_{t-1})+d(\sigma_{t-1},\sigma_t)].\)
Since each comparator ranking is fixed independently of the samples,
\(\mathbb E[f_{Q_t}(\sigma_{t-1})]=\sum_R\mu_t(R)f_R(\sigma_{t-1})=a_t(\sigma_{t-1}).\)
Taking expectations in the preceding comparator inequality yields
\(\mathbb E[\operatorname{OPT}_{\mathrm{pt}}(J)]\le\sum_{t=1}^T[a_t(\sigma_{t-1})+d(\sigma_{t-1},\sigma_t)]=\operatorname{OPT}(I).\)
Combining the two bounds proves
\(\boxed{\mathbb E[\operatorname{cost}(I)]\le C_0r^2\operatorname{OPT}(I).}\)
In particular, the argument never needs to compute either offline optimum.
Enumerate the current support as \(R_1,\ldots,R_{\tau_t}\), and write its masses as \(\mu_t(R_i)=p_i/q_i\), with positive integers encoded in binary.
Set \(D=\prod_i q_i\) and \(w_i=p_i(D/q_i)\). Then the weights are positive integers satisfying \(\sum_iw_i=D\). The bit length of \(D\) is at most the sum of the denominator bit lengths, hence is bounded by \(L_t\).
If \(D=1\), sampling is deterministic. Otherwise, put \(k=\lceil\log_2D\rceil\), draw \(k\) unbiased bits to obtain a uniform integer \(Z\) in \(\{0,\ldots,2^k-1\}\), and repeat until \(Z<D\). Each trial succeeds with probability \(D/2^k>1/2\), so the expected number of trials is less than two.
Return the unique \(R_i\) whose cumulative-weight interval contains \(Z\). This samples exactly from \(\mu_t\). Constructing the weights, performing rejection sampling, and locating the interval all take expected time polynomial in \(\tau_t,L_t\). This also covers dyadic masses.
For completeness, the DLM update maintains nonnegative budgets \(b(z)\), initially zero. On a request \(Q\) of size \(s\), let \(x\) be its first-ranked item and let \(\ell=\pi(x)\). It moves \(x\) to the front and resets its budget, adds \(\ell/s\) to each other requested item’s budget, and then repeatedly moves any item satisfying \(b(z)\ge\pi(z)\) to the front and resets its budget. These are [Routine 1 and Algorithm 2 of the cited paper](https://arxiv.org/html/2306.17755v1).
Here is an explicit bit-complexity bound for this implementation. At the end of each update, \(0\le b(z)<\pi(z)\le m\). This invariant holds initially. Moving an item to the front only increases other items’ positions, so it cannot create a new budget violation among them. Before the repeated-fetch loop, only the at most \(s-1\) items whose budgets were increased can violate the invariant. Each loop iteration removes its fetched item from this candidate set and creates no new candidate. Hence there are at most \(s-1\) loop iterations.
Represent every budget with the fixed denominator \(H=r!\). This is exact because every increment has denominator \(s\), where \(s\le r\) and \(s\) divides \(H\). At epoch boundaries, budget numerators are smaller than \(mH\). During an update, each increased budget receives at most \(m\), so numerators remain smaller than \(2mH\). Their bit lengths are therefore \(O(\log(m+1)+r\log(r+1))\), independently of the number of elapsed epochs.
Each update uses at most \(r\) moves to the front, each implementable by scanning and shifting a list of \(m\) items. Budget arithmetic and candidate scans consequently take polynomial time in \(m,r\), with bounded-size persistent state.
Together with exact sampling and reading the cohort encoding, this proves expected processing time polynomial in \(m,\tau_t,L_t,r\) per epoch. The construction and competitive proof therefore meet every requirement of the question.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The sampling reduction establishes the requested strict expected competitive guarantee, and the implementation bounds establish expected polynomial processing time per epoch. No major or minor mathematical issues were found.
The prover states the necessary theorem precisely: DLM starts from the prescribed initial ranking, handles nonempty requests of size at most \(r\), needs no horizon, and satisfies a strictly multiplicative bound against the dynamic offline optimum.
These claims match the cited source. Section 1.1 specifies access before reordering, movement measured by Kendall distance, and no knowledge of the sequence length. Theorem 13 explicitly gives strict \(O(r^2)\)-competitiveness in the dynamic scenario with the same initial permutation for the online and offline algorithms. Thus an additive initialization term is not being silently discarded. [Basiak–Bienkowski–Tatarczuk, Sections 1.1 and 5](https://arxiv.org/html/2306.17755v1)
The paper’s different use of letters for universe size and sequence length causes no mismatch. The theorem applies to every sampled sequence because each sampled request belongs to a support containing only nonempty sets of cardinality at most \(r\). If the sampled sequence has a smaller maximum request size, its guarantee still implies the stated bound using \(r\).
At epoch \(t\), the policy uses the revealed distribution and its existing DLM state. Its next ranking depends only on earlier samples and the current sample. It therefore is causal and does not require \(T\).
Only one DLM instance is maintained, so the construction chooses one shared ranking per epoch. Sampling a request internally does not replace the prescribed cohort access charge; the prover explicitly distinguishes actual cohort access from virtual point-request access.
The description follows the cited DLM update. Its permitted choice of any budget-violating item can be implemented deterministically using the maintained list order; the cited algorithm leaves that choice unrestricted. No additional mathematical hypothesis is needed. [Basiak–Bienkowski–Tatarczuk, Routine 1 and Algorithm 2](https://arxiv.org/html/2306.17755v1#S2)
Fixing \(I\) independently of the random bits is essential and is done explicitly.
Because the DLM state before epoch \(t\) depends only on earlier samples, conditioning on those samples fixes \(\pi_{t-1}\). The fresh sample retains distribution \(\mu_t\). Consequently, the displayed conditional expectation
\[
\mathbb E[f_{Q_t}(\pi_{t-1})\mid Q_1,\ldots,Q_{t-1}]
=a_t(\pi_{t-1})
\]
is correct.
The actual and virtual executions choose identical endpoint rankings. Their movement charges, defined as the Kendall distance between successive endpoint rankings, therefore agree realization by realization. This comparison does not require equating Kendall distance with the total number of swaps performed by an implementation containing several move-to-front operations.
For finite \(T\), every access charge is at most \(m\), and every endpoint movement charge is at most \(\binom m2\). Thus all relevant expectations are finite, and taking expectations and summing is legitimate.
Applying the point-request theorem separately to every realization yields exactly the inequality stated in Section 3.
An optimal cohort ranking sequence exists: there are finitely many feasible ranking sequences for any finite horizon.
The prover fixes such a sequence before considering the samples. Although it may depend on the entire cohort input, that input is fixed independently of the policy’s random bits. The comparator therefore remains independent of the sampled requests.
For each realization, this fixed ranking sequence is feasible for the point-request problem. Hence the sampled point-request optimum is bounded above by its sampled comparator cost. Taking expectations converts each comparator access charge into the corresponding cohort access charge, while its movement charges remain unchanged.
This proves
\[
\mathbb E[\operatorname{OPT}_{\mathrm{pt}}(J)]
\le \operatorname{OPT}(I).
\]
The argument does not interchange expectation and minimization as an equality, or assume that the sampled optimum uses sample-independent rankings. The inequality is sufficient, and combining it with Section 3 proves the requested guarantee with the universal constant \(C=C_0\).
For \(D=\prod_i q_i\), every \(D/q_i\) is an integer, so all weights \(w_i=p_i(D/q_i)\) are positive integers. Normalization of the masses gives \(\sum_i w_i=D\).
The bound on the bit length of \(D\) is correct: multiplying denominators adds their logarithms, so its binary length is bounded by the sum of their binary lengths, and hence by \(L_t\).
For \(D>1\), rejection sampling with \(k=\lceil\log_2D\rceil\) accepts with probability \(D/2^k>1/2\). Conditional on acceptance, the integer is uniform on the required range. The cumulative-weight intervals therefore produce precisely the prescribed probabilities.
Expected trials are fewer than two. All integer operations have polynomially bounded operand lengths, so weight construction and interval selection have expected polynomial bit complexity. The separate \(D=1\) case is handled correctly.
The budget invariant is preserved as written. Moving an item to the front increases or leaves unchanged every other item’s position, without increasing its budget. It therefore cannot create a new violation for another item.
Only the at most \(s-1\) items receiving budget increments can violate the invariant before the loop. Each loop iteration resets its selected item’s budget and creates no new violation. Thus there are at most \(s-1\) loop iterations, and at most \(s\le r\) move-to-front operations including the initial move.
The fixed denominator \(H=r!\) represents every increment exactly because every integer \(s\) with \(1\le s\le r\) divides \(H\). Boundary numerators are smaller than \(mH\); during an update they remain smaller than \(2mH\). The stated bit bound follows and is independent of the elapsed horizon.
List updates, budget arithmetic, and candidate scans consequently take polynomial time in \(m,r\). Computing \(H\) and initializing the state also take polynomial time. Combining these bounds with exact sampling establishes the required expected per-epoch processing bound.
The reasoning covers \(m=1\), \(r=1\), point-mass supports, and arbitrary finite horizons. For an empty horizon, if permitted, both costs are zero.
No repair is required. The output resolves the assigned existence question, including the strict multiplicative guarantee, shared-ranking requirement, causality, unknown horizon, and expected polynomial processing time. It does not claim an algorithm for computing the exact offline optimum.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.