Hardness of Online Sleeping Combinatorial Optimization Problems
This work addresses a theoretical gap for researchers in online learning and computational complexity, showing that sleeping versions of common problems are computationally intractable, which is incremental as it builds on prior hardness conjectures.
The paper tackles the computational hardness of online combinatorial optimization problems in the sleeping setting, where actions become unavailable each round, showing that these problems are at least as hard as PAC learning DNF expressions, an open problem, and resolves a specific open problem for Online Shortest Paths.
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).