Catch them if you can
Catch them if you can
复制标题
如果可以的话抓住他们
DOI：
10.1145/2422436.2422489
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Cygan M
中科院分区：
文献类型：
--
作者：
Cygan M
考虑以下为不耐烦的用户提供服务的问题：我们得到了一组我们想要服务的客户。我们在每个时间步中最多可以服务一个客户（为服务客户 i 获得价值 vi）。在每个时间步骤结束时，每个尚未获得服务的客户 i 以概率 qi 独立离开系统，并且永远不会返回。我们应该使用什么策略来服务客户，以最大化收集到的期望价值？竞争分析的标准模型可以应用于这个问题：选择价值最大的客户给我们提供了最优算法获得的价值的一半，而使用顶点加权在线匹配算法给我们提供了最优算法的 1-1/e ~ 0.632 分数。正如竞争分析中常见的那样，这些近似值与了解客户所有投掷硬币的有洞察力的对手所能实现的最佳价值进行比较。我们能做得更好吗？如果我们将我们的性能与这样的透视算法进行比较，我们会显示上限约为 0.648，这表明我们无法大幅提高我们的性能。然而，这些都是与更强大的对手的悲观比较：如果我们将自己与这个问题的最佳策略进行比较，而该策略不具有不公平的优势，该怎么办？在这种情况下，我们可以做得更好：特别是，我们给出的算法的期望值至少是最优算法可实现的值的 0.7。这种改进是通过新颖的舍入算法和非局部分析实现的。
Consider the following problem ofserving impatient users: we are given a set of customers we would like to serve. We can serve at most one customer in each time step (getting value vifor serving customer i). At the end of each time step, each as-yet-unserved customer i leaves the system independently with probability qi, never to return. What strategy should we use to serve customers to maximize the expected value collected?The standard model of competitive analysis can be applied to this problem: picking the customer with maximum value gives us half the value obtained by the optimal algorithm, and using a vertex weighted online matching algorithm gives us 1-1/e ~ 0.632 fraction of the optimum. As is usual in competitive analysis, these approximations compare to the best value achievable by an clairvoyant adversary that knows all the coin tosses of the customers. Can we do better?We show an upper bound of ~0.648 if we compare our performance to such an clairvoyant algorithm, suggesting we cannot improve our performance substantially. However, these are pessimistic comparisons to a much stronger adversary: what if we compare ourselves to the optimal strategy for this problem, which does not have an unfair advantage? In this case, we can do much better: in particular, we give an algorithm whose expected value is at least 0.7 of that achievable by the optimal algorithm. This improvement is achieved via a novel rounding algorithm, and a non-local analysis.
登录
查看更多内容
DOI：
--
发表时间：
2001
期刊：
影响因子：
--
作者：
Timothy I. Bell
通讯作者：
Timothy I. Bell
DOI：
--
发表时间：
2006
期刊：
影响因子：
--
作者：
S. Quarteroni;S. Manandhar
通讯作者：
S. Manandhar
学习安全中的开放性问题
DOI：
--
发表时间：
2008
期刊：
Security and Artificial Intelligence
影响因子：
--
作者：
M. Barreno;P. Bartlett;F. J. Chi;A. Joseph;B. Nelson;Benjamin I. P. Rubinstein;Udam Saini;J. D. Tygar
通讯作者：
J. D. Tygar
交互式相关反馈中相关反馈质量和数量的影响：基于用户建模的模拟
DOI：
--
发表时间：
2006
期刊：
European Conference on Information Retrieval
影响因子：
--
作者：
Heikki Keskustalo;K. Järvelin;Ari Pirkola
通讯作者：
Ari Pirkola
关于用户生成的元数据在视听收藏中的作用
DOI：
--
发表时间：
2011
期刊：
International Conference on Knowledge Capture
影响因子：
--
作者：
R. Gligorov;M. Hildebrand;J. V. Ossenbruggen;G. Schreiber;Lora Aroyo
通讯作者：
Lora Aroyo