Online Selection with Uncertain Disruption
研究平台在面临中断风险时如何在线选择请求，提出阈值算法并证明非自适应策略的竞争比为e/(e-1)，自适应策略可提升至约0.745。
Online Selection with Uncertain Disruption Many digital and service platforms must decide whether to accept a current request or wait for a potentially better one. This trade-off becomes more challenging when serving a request may unexpectedly disrupt future operations. In the paper “Online Selection with Uncertain Disruption,” Yihua Xu, Süleyman Kerimov, and Sebastian Perez-Salazar introduce a model for such settings, where a decision maker observes values sequentially and each accepted value may trigger a disruption that stops the process. The paper develops simple threshold-based algorithms and evaluates them through competitive analysis against a clairvoyant benchmark that knows all values but still faces disruption uncertainty. The authors show that a nonadaptive single-threshold algorithm achieves the tight competitive ratio [Formula: see text], whereas adaptive threshold policies improve the asymptotic guarantee to approximately 0.745. The results connect disruption-aware online selection with classical prophet inequalities and quantify the value of adaptivity under operational uncertainty.