.png){kind=icon}
返回
ORDER-COMPETITIVE RATIO
.png){kind=icon}
PRE
AI
DOI：10.1137/24M1708917.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
我们提出了一种衡量贝叶斯环境下在线算法性能的新指标，其中输入来自已知先验分布，但实现值以在线方式逐个揭示。我们称该新指标为顺序竞争比。它被定义为（在所有分布序列中最坏情况下）无序感知算法与有序感知算法性能的比值，量化了因缺乏到达顺序知识而造成的损失。尽管在线算法性能中到达顺序的作用日益受到关注，但这种损失此前一直被忽视。我们在范式化的先知不等式问题中研究了顺序竞争比，针对两种常见目标函数（i）最大化期望值和（ii）最大化获得最大值的概率，以及两种算法族（i）自适应算法和（ii）单阈值算法。我们为所有四种组合提供了确定性算法的紧界，并给出了随机算法的初步结果。我们的分析需要新思路并偏离了标准技术。特别是，我们的自适应算法必然超越单阈值算法。与经典竞争比指标不同（其中最优性能由确定性单阈值算法实现），我们的顺序竞争比结果体现了自适应算法可能比单阈值算法更强大，且随机算法优于确定性算法的直觉。
Keyword:
online algorithms
order-competitive ratio
prophet inequality
期刊
S
IF:
1.6
论文数:
14
被引数:
0
查看更多机构
.png){kind=icon}
