The Competitive Ratio of Online Budgeted Allocation is Strictly Smaller than $1-1/e$

概要

A well-known conjecture in online algorithms is that the (randomized) competitive ratio of online budgeted allocation is $1-1/e$. We refute this conjecture and show that every randomized online algorithm has competitive ratio at most $1 - 1/e - \varepsilon$ for a (small) absolute constant $\varepsilon > 0$.

参考リンク

• Paper ↗

リンク先のライセンス・再現性・データ条件をご確認ください。自動分類や実装の目安は保証ではありません。

実装を始めるプロンプト

参考リンクを確認したうえで、次の内容をコピーして利用できます。

# 論文・記事
The Competitive Ratio of Online Budgeted Allocation is Strictly Smaller than $1-1/e$

# 概要
A well-known conjecture in online algorithms is that the (randomized) competitive ratio of online budgeted allocation is $1-1/e$. We refute this conjecture and show that every randomized online…

# 原典
https://arxiv.org/abs/2610.41136

上記の手法を実装してください。実行前に依存関係とライセンスを確認してください。