For the online combinatorial allocation problem with subadditive valuations, Correa and Cristi (STOC 2023) proved the existence of a $6$-competitive online algorithm, improving on the previous best $O(\log\!\log m)$-competitive online algorithm due to D\"utting, Kesselheim, and Lucier (FOCS 2020), where $m$ is the numb...
Calum MacRury, Rian Neogi, Kanstantsin Pashkovich et al.· 0 citations
We study online allocation problems where $n$ requests over $m$ resources arrive in an adversarial order and must be served immediately and irrevocably. This framework captures both Online Resource Allocation, where the goal is to maximize value subject to resource budgets, and Online Load Balancing, where the goal is...
Matthew Faw, Sahil Singla, Yi-Fan Wang· 0 citations
Competitive analysis is central to the study of online algorithms, but upper bounds are often highly problem-specific. We develop a more unifying methodology via the minimax viewpoint. Guided by Yao's principle, we reduce worst-case competitive analysis to Bayesian online design under an arbitrary correlated prior over...
Thomas Kesselheim, Marco Molinaro, Kalen Patton et al.· 1 citation
A random preview can replace worst-case sequential complexity by classical statistical dimensions without randomizing the online order by using an online analogue of chaining, implemented as a multiscale aggregation algorithm rather than only as an analytic argument.
Roi Livni, Sahil Singla· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
