2024/05/16 by Nicolas Christianson, Christianson, Nicolas, Bo Sun +5 · 1 citation
Computer Science · Engineering · #Advanced Wireless Network Optimization #Caching and Content Delivery #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2405.09859
openalex publication_date 2024/05/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the design of risk-sensitive online algorithms, in which risk measures are used in the competitive analysis of randomized online algorithms. We introduce the CVaRδ-competitive ratio (δ-CR) using the conditional value-at-risk of an algorithm's cost, which measures the expectation of the (1-δ)-fraction of worst outcomes against the offline optimal cost, and use this measure to study three online optimization problems: continuous-time ski rental, discrete-time ski rental, and one-max search. The structure of the optimal δ-CR and algorithm varies significantly between problems: we prove that the optimal δ-CR for continuous-time ski rental is 2-2-Θ((1)/(1-δ)), obtained by an algorithm described by a delay differential equation. In contrast, in discrete-time ski rental with buying cost B, there is an abrupt phase transition at δ= 1 - Θ((1)/(log B)), after which the classic deterministic strategy is optimal. Similarly, one-max search exhibits a phase transition at δ= (1)/(2), after which the classic deterministic strategy is optimal; we also obtain an algorithm that is asymptotically optimal as δ\downarrow 0 that arises as the solution to a delay differential equation.