online resource allocators

Abstract: We study online graph coloring in the random-arrival model, where the vertices are presented in a uniformly random order. Assuming $n$ and $k$ are known in advance, we present a randomized exponential-time algorithm that colors any $k$-colorable graph on $n$ vertices with $O(k^3 \log^2 k \log^4 n)$ colors in expectation. This is the first online coloring algorithm that uses a polylogarithmic number of colors for all fixed $k \geq 3$, and is better than a known lower bound of $Ω(\log^{k-1} n)$ colors under adversarial arrivals for all fixed $k \geq 6$. In addition, assuming $n$ is known in advance, we obtain a competitive ratio of $\widetilde{O}(n^{2/3})$. For comparison, it is known to be NP-hard to approximate (offline) graph coloring within a factor of $n^{1-\varepsilon}$ for all fixed $\varepsilon > 0$. Therefore, our exponential-time online algorithm achieves a performance guarantee beyond the NP-hardness threshold for polynomial-time approximation algorithms.

Abstract: We study prophet inequalities under intersections of $q$ partition matroids, where an online algorithm irrevocably selects elements with independent nonnegative values drawn from known distributions and revealed in an adversarial order. We prove an $Ω(q/\log q)$ lower bound on the competitive ratio. Together with the known $O(q)$ upper bounds, this resolves, up to a logarithmic factor, the optimal dependence on $q$, an open question posed by Correa, Cristi, Fielbaum, Pollner, and Weinberg (IPCO 2022) and Saxena, Velusamy, and Weinberg (ITCS 2023). Our construction also yields an $Ω(d/\log d)$ lower bound for $d$-single-minded auctions, where buyers request fixed bundles of at most $d$ unit-capacity items. Our construction and analysis build on the "big-decisions-first" framework of Rubinstein and Singla (STOC 2026).