22 problems
For every and every fixed sequence of unordered edges on the vertex set , there exists a randomized online algorithm that orients each edge i…
Consider online allocation with agents having monotone submodular valuation functions . Items arrive sequentially, and each item must be irrev…
For every matroid and every nonnegative weight function , when the elements of arrive in a uniformly random order and their weight…
This entry tracks Online graph-coloring competitive-ratio conjectures. The result establishes an asymptotic randomized-versus-deterministic separation against oblivious adversaries…
Optimal expected online discrepancy conjecture. For all ,
Let be the graph in the paper's online model, let be the set selected by an online algorithm , and let be the set of all future edges ever rev…
Let be the random bipartite graph in the online model considered in the source, let be the balance parameter, and let denote th…
Constant-playability relaxation. Let be a graph without isolated edges. Then there exists a constant such that is -unbalanceable, where
St. Ives matching conjecture. For all , there is a constant such that for all ,
Let a -strategy of Builder be a strategy that observes at most arriving edges and purchases at most of them. A graph is Hamiltonian if it contains a Hamilton cyc…
Let be a positive integer, let , and let a -strategy of Builder be a strategy that observes at most arriving edges and purchases at most of th…
Kurek–Ruciński conjecture.
Let be a sequence of vectors with Euclidean norm at most . In the oblivious adversarial online setting, the algorithm receives at time …
Let denote the family of convex sets in , let be the set of finite strings with alphabet , and let an online selector be a map sat…
Let and let . A greedy-Haar -thinning strategy produces a sequence , and write for its first…
Let be an online binary search tree algorithm. Starting with any initial tree with elements, let be the preorder sequence of a binary search tree t…
Let be an online binary search tree algorithm. Starting with any initial tree with elements, consider any sequence of splits. A split at an element …
Let be an online binary search tree algorithm. Starting with any initial tree with elements, consider inserting or deleting the current minimum or maximum e…
Let be a graph and let . The on-line chromatic number conjecture. Deciding whether … is textsc{PSPACE}-complete. The complexity of deciding whether the on-line…
On-line ranking conjecture. There exist universal constants and satisfying such that
Let be fixed in , let denote the size of the lookahead window, and let be the best achievable delay under policies…
Let be a graph, with vertex number , chromatic number , and on-line choice number . A graph is on-line chromatic-choosable when…