Summary: This paper proposes an algorithm for online linear optimization problem over permutations; the objective of the online algorithm is to find a permutation of \(\{1,\ldots ,n\}\) at each trial so as to minimize the “regret” for \(T\) trials. The regret of our algorithm is \(O(n^2 \sqrt{T \ln n})\) in expectation for any input sequence. A naive implementation requires more than exponential time. On the other hand, our algorithm uses only \(O(n)\) space and runs in \(O(n ^{2})\) time in each trial. To achieve this complexity, we devise two efficient algorithms as subroutines: One is for minimization of an entropy function over the permutahedron \(P _{n }\), and the other is for randomized rounding over \(P _{n }\).
For the entire collection see [Zbl 1228.68006].