Hardness of Online Sleeping Combinatorial Optimization Problems
Abstract
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].
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].
Research Areas
