Combinatorial Online Prediction via Metarounding
Combinatorial Online Prediction via Metarounding
复制标题
DOI：
10.1007/978-3-642-40935-6_6
复制
发表时间：
2013-10
期刊：
影响因子：
--
通讯作者：
Takahiro Fujita;Kohei Hatano;Eiji Takimoto
中科院分区：
文献类型：
--
作者：
Takahiro Fujita;Kohei Hatano;Eiji Takimoto
我们考虑组合概念的在线预测问题。这样的概念的例子包括-tpaths，置换，真值分配，集合覆盖，等等。在线预测算法的目标是在事后与最佳固定组合概念竞争。一个通用的方法来解决这个问题是设计一个在线预测算法使用相应的离线（近似）算法作为一个预言。然而，目前最先进的方法不够有效。本文提出了一种更有效的在线预测算法时，离线近似算法的完整性间隙的保证。
We consider online prediction problems of combinatorial concepts. Examples of such concepts includes-tpaths, permutations, truth assignments, set covers, and so on. The goal of the online prediction algorithm is to compete with the best fixed combinatorial concept in hindsight. A generic approach to this problem is to design an online prediction algorithm using the corresponding offline (approximation) algorithm as an oracle. The current state-of-the art method, however, is not efficient enough. In this paper we propose a more efficient online prediction algorithm when the offline approximation algorithm has a guarantee of the integrality gap.