arXiv:2608.01616cs.LGcs.DS2026-08

用后验匹配思想统一解决在线优化问题,性能接近最优。

Online Algorithms via Minimax and Posterior Matching

  • 基于后验匹配原则设计在线算法,跟踪最优解的更新
  • 对集合覆盖、负载均衡等经典问题实现最优或近优性能
  • 适用于带相关先验的复杂场景,适合研究在线算法的学者

竞争性分析是在线算法研究的核心,但上界通常高度依赖具体问题。本文从极小化极大视角出发,将最坏情况的竞争分析转化为任意相关先验下的贝叶斯在线设计问题。令 $X^*$ 为真实实例的后验最优分数解,$X^{(t)} = \mathbb E[X^* \mid \mathcal F_t]$ 为其后验过程。核心策略为后验匹配:在每一步 $t$,选择在在线约束允许下最贴近当前后验 $X^{(t)}$ 的可行动作。该原则可导出多个经典在线分数问题(如集合覆盖、负载均衡、匹配及更一般的资源分配)的最优或近优保证,涵盖范数与凹目标情形,恢复或改进现有最优界。通过已知取整约简,还可得到加权页替换、星型度量上的MTS及滑雪租赁问题的随机整数解保证。技术上,分析将竞争性保证归约为后验最优解生成的向量鞅的关键概率不等式。该框架提供了一条从任意相关先验下的贝叶斯在线设计到信息论意义的最坏情况竞争保证的通用路径。

原文摘要 · Abstract (English)

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 arrival sequences. For such a prior, let $X^*$ be the hindsight-optimal fractional solution for the realized instance, and let $X^{(t)}=\mathbb E[X^*\mid \mathcal F_t]$ be its posterior process. Our guiding rule is posterior matching: at each time $t$, choose the feasible online action that tracks the current posterior $X^{(t)}$ as closely as the online constraints permit. We show that this single principle yields optimal or near-optimal guarantees for several classical online fractional problems, including set cover, load balancing, matching and more general resource-allocation problems, recovering or improving state-of-the-art bounds in these settings with norm/concave objectives. Via known rounding reductions, it also yields randomized integral guarantees for weighted paging, MTS on star metrics, and ski-rental. At a technical level, our analysis reduces competitive guarantees to key probabilistic inequalities for the vector martingales generated by the posterior of the offline optimum. The resulting framework gives a reusable route from Bayesian online design under arbitrary correlated priors to information-theoretic worst-case competitive guarantees.

在线算法后验匹配竞争分析贝叶斯设计

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。