Online Linear Optimization over Permutations
Online Linear Optimization over Permutations
复制标题
DOI：
10.1007/978-3-642-25591-5_55
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Shota Yasutake;Kohei Hatano;S. Kijima;Eiji Takimoto;M. Takeda
中科院分区：
文献类型：
--
作者：
Shota Yasutake;Kohei Hatano;S. Kijima;Eiji Takimoto;M. Takeda
本文提出了一种求解排列上线性优化问题的在线算法，该算法的目标是在每次试验中找到一个{1，.，n}的排列，以使T次试验的“遗憾”最小.算法的缺点是对任意输入序列都有期望值。一个简单的实现需要的时间超过指数级。另一方面，我们的算法仅占用O（n）空间，每次试验运行时间为O（n2）。为了实现这种复杂性，我们设计了两个有效的算法作为子程序：一个是最小化的熵函数在thepermutahedronPn，另一个是随机舍入在Pn。
This paper proposes an algorithm foronline linear optimization problem over permutations; the objective of the online algorithm is to find a permutation of {1,…,n} at each trial so as to minimize the “regret” forTtrials. The regret of our algorithm isin expectation for any input sequence. A naive implementation requires more than exponential time. On the other hand, our algorithm uses onlyO(n) space and runs inO(n2) time in each trial. To achieve this complexity, we devise two efficient algorithms as subroutines: One is for minimization of an entropy function over thepermutahedronPn, and the other is for randomized rounding overPn.