跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2611.17083 · v1

List Update with Time Windows and Delays without Batch-Serving

带时间窗口与延迟的列表更新:非批量服务模型

首次提交 2026-11-13 00:50
版本更新 2026-11-13 00:50
雷达观测 2026-11-13 14:15
arXiv ↗PDF ↗

摘要

We study list update with time windows and delays when every request requires a separate access. Unlike batch-serving models, serving several requests to one element still incurs one access per request, and each access may change the list for subsequent requests. For time windows of overlap at most k≥2k\ge2, our deterministic First-Element Removal algorithm is (3−2/k)(3-2/k)-competitive, hence 33-competitive in general. Against an oblivious adversary, a randomized adaptation of BIT is 7/47/4-competitive on arbitrary 22-overlap inputs. More generally, on inputs without self-overlap, it is (13/4−9/[2(k+1)])\left(13/4-9/[2(k+1)]\right)-competitive for every k≥2k\ge2. For delays, we give a deterministic 55-competitive algorithm and a lower bound of 2+32+\sqrt3 for deterministic delay-unaware algorithms. Our analyses extend inversion potentials with per-request credits that reconcile different service times and orders.

AI 论文解读

基于摘要 · 非全文审阅

研究每次请求都需单独访问的列表更新问题,在时间窗口重叠度受限和延迟场景下给出竞争比分析与算法。

正在读取账号与研究记录…

版本差异

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

观测到的版本

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

v1 · 2026-11-13 00:50 · 最新观测版本

List Update with Time Windows and Delays without Batch-Serving

We study list update with time windows and delays when every request requires a separate access. Unlike batch-serving models, serving several requests to one element still incurs one access per request, and each access may change the list for subsequent requests. For time windows of overlap at most k≥2k\ge2, our deterministic First-Element Removal algorithm is (3−2/k)(3-2/k)-competitive, hence 33-competitive in general. Against an oblivious adversary, a randomized adaptation of BIT is 7/47/4-competitive on arbitrary 22-overlap inputs. More generally, on inputs without self-overlap, it is (13/4−9/[2(k+1)])\left(13/4-9/[2(k+1)]\right)-competitive for every k≥2k\ge2. For delays, we give a deterministic 55-competitive algorithm and a lower bound of 2+32+\sqrt3 for deterministic delay-unaware algorithms. Our analyses extend inversion potentials with per-request credits that reconcile different service times and orders.

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