59 problems

Beck–Fiala conjecture. Every such matrix satisfies

The deterministic $k$-server conjecture. There exists a deterministic online algorithm for the $k$-server problem with competitive ratio $k$.

Frieze–Krivelevich–Michaeli conjecture. Any strategy that uses $\varepsilon n$ fewer edges than the greedy strategy, for any constant $\varepsilon>0$, fails with high probability.

Future-edge conjecture. For every $\epsilon>0$ and $r\in\mathbb{N}$, there is a constant $c_{\epsilon,r}>0$ and an online algorithm satisfying, with high probability, the following…

Consider the rendezvous problem on the real line in which two players start at distance two and have no common orientation, and let the competitive ratio be the ratio of the meetin…

Optimal expected online discrepancy conjecture. For all $2\leq d\leq n/2$,

Let $G$ be the graph in the paper's online model, let $\mathcal{A}(G)$ be the set selected by an online algorithm $\mathcal{A}$, and let $E$ be the set of all future edges ever rev…

Let $G_{\mathrm{bip}}(n,p)$ be the random bipartite graph in the online model considered in the source, let $\gamma$ be the balance parameter, and let $\alpha_{\rm COMP}$ denote th…

Let $n$ be a natural number, let ${\mathcal T}$ be a set of trees on vertex set $[n]$, let $\mu$ be a probability distribution on ${\mathcal T}$, and let…

In a two-way dynamic matching network, let $\mathbf{TP}$ denote the local availability-based policy proposed by Kerimov et al. The policy makes matching decisions using agent avail…

Constant-playability relaxation. Let $G=(V,E)$ be a graph without isolated edges. Then there exists a constant $c\in\mathbb{N}\cup\{0\}$ such that $G$ is $f$-unbalanceable, where

Let $K$ denote the number of epochs in the throughput-constrained online resource allocation model, and let the algorithm's regret be measured as a function of $K$. Regret-dependen…

Nonintegral-decision extension conjecture. A similar $\Omega(T)$ regret lower bound should hold even without the integrality assumption on the online algorithm's decisions.

Let $\textsf{RAND}$ be Fleischer's randomized algorithm for the Bahncard problem $\operatorname{BP}(C,\beta,T)$, and suppose that for $T=\infty$ it is $e/(e-1+\beta)$-competitive.…

Let $G$ be an online graph on $n$ vertices with maximum degree $Delta=omega(\log n)$, and let $\mathcal{A}$ be the randomized greedy algorithm that, for a fixed color set, colors e…

Coffman–Kadota–Shepp conjecture. The first-fit discipline is asymptotically optimal for non-degenerate $H$.

Budget conjecture. For every constant $\varepsilon>0$, if Builder follows any $(\tau_k,(o_k-\varepsilon)n)$-strategy, then with high probability her graph fails to have minimum deg…

A binary search tree algorithm is $O(1)$-competitive if its cost is at most a constant multiple of the cost of the optimum offline binary search tree on every access sequence. Dyna…

Consider an online binary search tree algorithm, and compare its cost on an access sequence with the cost of the optimum offline binary search tree. The sequence has length…

Rank-greater-than-two conjecture. This mechanism is $2$-competitive for $k>2$.

Uniform-matroid conjecture. A straightforward generalization of this policy achieves a guarantee of $1/2$ for all uniform matroids.

Randomized metrical task systems conjecture. The asymptotically tight $\Theta(\log n)$ competitive-ratio bound holds in all metric spaces.

St. Ives matching conjecture. For all $k\geq 1$, there is a constant $c_k$ such that for all $n\geq 1$,

Intersection-free matching conjecture. For every intersection-free matching $M$, there is a constant $c$ such that

Let $k$ be a positive integer, let $\varepsilon>0$, and let a $(t,b)$-strategy $B$ of Builder be a strategy that observes at most $t$ arriving edges and purchases at most $b$ of th…