跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2611.11133 · v1

Online Correlated Exponential Clocks

首次提交 2026-11-08 12:52
版本更新 2026-11-08 12:52
雷达观测 2026-11-10 12:16
arXiv ↗PDF ↗

摘要

In online resource allocation, we seek to allocate an incoming sequence of requests j∈Jj \in J among a set of offline resources i∈Ii \in I, where decisions must be made immediately without knowledge of the future. State-of-the-art results typically follow from relax-and-round methods. For many problems, recent advances have come from improved methods of online rounding with negative correlations. However, such rounding schemes have largely been implemented on a case-by-case basis, making it difficult to transfer improvements and new ideas between problem settings. This leads us to ask the question: Can we develop unified methods of online rounding with negative correlations which can obtain state-of-the-art guarantees across different resource allocation settings? We answer this question affirmatively by introducing the framework of Online Correlated Exponential Clocks (OCEC). In this framework, fractional allocations xijx_{ij} are assigned exponential clocks Yij∼Exp(xij)Y_{ij} \sim \mathrm{Exp}(x_{ij}), and each request jj is allocated to the resource ii with smallest YijY_{ij}. The key idea is that the sequence (Yij)j(Y_{ij})_j for each fixed ii is negatively correlated via an OCEC generator, resulting in better-than-baseline guarantees. Our contributions are two-fold: First, we introduce OCEC rounding as a problem-independent interface which any online algorithm can use. This isolates the challenge of online rounding into the self-contained problem of designing an effective OCEC generator. Second, we demonstrate the flexibility of this method by giving a single OCEC generator which yields improved competitive bounds in three distinct problems: 0.556 for Display Ads, 0.530 for AdWords, and 4.69 for squared-load balancing. Previous best results were obtained by Blanc and Charikar (FOCS 2021), Chen, Huang, and Sun (FOCS 2024), and Borst and Kashaev (SODA 2027), respectively.

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

目前只收录了一个版本。收录下一版后,可以对照标题、作者、分类和摘要。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v1 · 2026-11-08 12:52 · 最新观测版本

Online Correlated Exponential Clocks

In online resource allocation, we seek to allocate an incoming sequence of requests j∈Jj \in J among a set of offline resources i∈Ii \in I, where decisions must be made immediately without knowledge of the future. State-of-the-art results typically follow from relax-and-round methods. For many problems, recent advances have come from improved methods of online rounding with negative correlations. However, such rounding schemes have largely been implemented on a case-by-case basis, making it difficult to transfer improvements and new ideas between problem settings. This leads us to ask the question: Can we develop unified methods of online rounding with negative correlations which can obtain state-of-the-art guarantees across different resource allocation settings? We answer this question affirmatively by introducing the framework of Online Correlated Exponential Clocks (OCEC). In this framework, fractional allocations xijx_{ij} are assigned exponential clocks Yij∼Exp(xij)Y_{ij} \sim \mathrm{Exp}(x_{ij}), and each request jj is allocated to the resource ii with smallest YijY_{ij}. The key idea is that the sequence (Yij)j(Y_{ij})_j for each fixed ii is negatively correlated via an OCEC generator, resulting in better-than-baseline guarantees. Our contributions are two-fold: First, we introduce OCEC rounding as a problem-independent interface which any online algorithm can use. This isolates the challenge of online rounding into the self-contained problem of designing an effective OCEC generator. Second, we demonstrate the flexibility of this method by giving a single OCEC generator which yields improved competitive bounds in three distinct problems: 0.556 for Display Ads, 0.530 for AdWords, and 4.69 for squared-load balancing. Previous best results were obtained by Blanc and Charikar (FOCS 2021), Chen, Huang, and Sun (FOCS 2024), and Borst and Kashaev (SODA 2027), respectively.

查看此版本解读 →查看此版本原文 ↗