We show that several online combinatorial optimization problems that admit efficient no-regret algorithms become computationally hard in the sleeping setting where a subset of actions becomes unavailable in each round. Specifically, we show that the sleeping versions of these problems are at least as hard as PAC learning DNF expressions, a long standing open problem. We show hardness for the sleeping versions of Online Shortest Paths, Online Minimum Spanning Tree, Online k-Subsets, Online k-Truncated Permutations, Online Minimum Cut, and Online Bipartite Matching. The hardness result for the sleeping version of the Online Shortest Paths problem resolves an open problem presented at COLT 2015 [Koolen et al., 2015].
展开▼
机译：我们展示了一些在线组合优化问题，这些问题允许有效的无悔算法在睡眠设置中很难进行计算，而睡眠设置中的每个动作子集都不可用。具体来说，我们证明这些问题的休眠版本至少与学习DNF表达式的PAC一样困难，这是一个长期存在的开放性问题。我们显示在线最短路径，在线最小生成树，在线k子集，在线k截断排列，在线最小割和在线二分匹配的休眠版本的硬度。睡眠版本的“在线最短路径”问题的硬度结果解决了在COLT 2015上提出的一个开放性问题[Koolen et al。，2015]。
展开▼
