We study the proportional online knapsack problem with removal. For randomized algorithms, we tighten the gap between the current lower and upper bounds on the expected competitive ratio by presenting a lower bound of roughly 1.27. We further study this problem under the model of online algorithms with predictions. Our lower bound arguments are agnostic to the type of available prediction, which makes them very general. For deterministic algorithms, we provide a tightly matching upper bound on the competitive ratio for a specific kind of weight prediction.

Graph coloring is a notoriously challenging problem, especially when considering the online setting where each arriving vertex must be colored immediately and irreversibly. Even on trees, which are trivially two-colorable, achieving anything better than a logarithmic competitive ratio becomes impossible if the order of arrival is adversarially determined. We investigate tree coloring in a slightly relaxed model where vertices arrive online but in random order, focusing specifically on algorithms with predictions of varying reliability. Furthermore, we extend our analysis to all two-colorable graphs and provide matching lower bounds for both cases.

Abstract We study the relationship between the competitive ratio and the tail distribution of randomized online problems. To this end, we identify a broad class of online problems for which the existence of a randomized online algorithm with constant expected competitive ratio r implies the existence of a randomized online algorithm that has a competitive ratio of $$(1+\varepsilon )r$$ ( 1 + ε ) r with high probability, measured with respect to the optimal profit or cost, respectively. The class of problems includes some of the well-studied online problems such as paging, k-server, and metrical task systems on finite metric spaces.

The non-uniform version of Turing machines with an extra advice input tape that depends on the length of the input but not the input itself is a well-studied model in complexity theory. We investigate the same notion of non-uniformity in weaker models, namely one-way finite automata. In particular, we are interested in the power of two-sided bounded-error randomization, and how it compares to determinism and non-determinism. We show that for unlimited advice, randomization is strictly stronger than determinism, and strictly weaker than non-determinism. However, when the advice is restricted to polynomial length, the landscape changes: the expressive power of determinism and randomization does not change, but the power of non-determinism is reduced to the extent that it becomes incomparable with randomization.

We study the relationship between the competitive ratio and the tail distribution of randomized online problems. To this end, we define a broad class of online problems that includes some of the well-studied problems like paging, k-server and metrical task systems on finite metrics, and show that for these problems it is possible to obtain, given an algorithm with constant expected competitive ratio, another algorithm that achieves the same solution quality up to an arbitrarily small constant error with high probability; the "high probability" statement is in terms of the optimal cost. Furthermore, we show that our assumptions are tight in the sense that removing any of them allows for a counterexample to the theorem.

Probabilistic computations can be very powerful with respect to space complexity, e.g. for logarithmic space, zero probability of error is equivalent to nondeterminism. This power, however, depends on the possibility of infinite computations. A natural open question is if this feature is necessary. We answer the question for sweeping finite automata (SFAs), i.e. two-way finite automata that can change the direction of head motion at endmarkers only. We show that zero probability of error SFAs allowing infinite computations can be exponentially more succinct than zero probability of error SFAs forbidding them. We also provide a strengthened form of this result showing that forbidding infinite computations can not be traded for the more powerful bounded-error probabilistic model. To prove our results, we introduce a technique for proving lower bounds on space complexity of SFAs that generalizes the notion of generic words discovered by M. Sipser.