Aug 2026· Theoretical Computer Science· Vol 1085, pp. 116195· 0 citations· 8 references
Computer ScienceMathematics
TL;DR
It is shown that a deterministic memoryless one-directional revoking algorithm achieves a competitive ratio of 0.786 on the simple chain in the random order model, which is worse than the basic greedy algorithm without revoking but better than any deterministic revoking algorithm in the adversarial model.
Abstract
A set of intervals $I = \{ I_1, I_2, \dots, I_n \}$ forms a simple chain if, for every $2\leq i \leq n-1$, interval $I_i$ overlaps only with $I_{i-1}$ and $I_{i+1}$. We show that a deterministic memoryless one-directional revoking algorithm achieves a competitive ratio of $2(1 - 1/\sqrt{e}) \approx 0.786$ on the simple chain in the random order model, hence performs worse than the basic greedy algorithm without revoking that has a competitive ratio of $(1 - 1/e^2) \approx 0.864$, but better than any deterministic revoking algorithm in the adversarial model that has a competitive ratio of at most $0.75$. The proof of the latter also leads to a lower bound of $n/4$ for the advice complexity.
Collapsing a $T^{\kappa^+}_{\omega_1}$-Ramsey cardinal $\kappa$ to $\omega_2$ gives, for every countable coloring of $[\omega_2]^2$, a stationary set $X$ and a color $i$ such that every finite subset of $X$ has stationarily many color-$i$ common neighbors in $X$. The color-$i$ graph on $X$ has diameter at most two afte...
This paper identifies the threshold at which sparsity begins to govern the online discrepancy of the random Beck--Fiala model, where the independent uniformly random vectors are independent of the sparsity up to constant factors.
Let $\Omega_n$ denote the set of $n\times n$ doubly stochastic matrices. Kim and Roush conjectured in 1981 that, for $n=2k+1>1$, $ \max_{A\in\Omega_{2k+1}}\operatorname{per}(I-A)=3\cdot 2^{k-2}$. They proposed the block construction $A_\star=\frac12(J_3-I_3)\oplus P_2^{\oplus(k-1)}$, where $P_2=\begin{pmatrix}0&1\\1&0\...
Comparison with the running mean highlights the stationary insertion-length distribution, its time-homogeneous update, stationary coefficient profile, and fixed effective memory, and its time-homogeneous update, stationary coefficient profile, and fixed effective memory.
A shift-chain is an $ r $-uniform hypergraph $ \mathcal{H} $ on vertex set $ [n] $ with the property that, for any two edges $ \{ e_1, \ldots, e_r \} $ and $ \{ f_1, \ldots, f_r \} $ with $ e_1<\cdots<e_r $ and $ f_1<\cdots<f_r $, either $ e_i \le f_i $ for all $ i \in [r] $ or $ f_i \le e_i $ for all $ i \in [r] $. It...
Consider $n$ independent, non-negative, mean at most one random variables, $X_1,X_2,\ldots$. We show the following bound on the probability of their sum exceeding a threshold $t$: \[ \mathbb{P}\left[\sum_{i=1}^n X_i\ge t\right] \leq 1-\left(1-\frac{1}{t}\right)^n \text{ for all } t\ge 2n+1 \,. \] To prove this, we cons...
P. Strack, Jannik M. Westermann· 1 citation
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
