Poster
Hardness of Online Sleeping Combinatorial Optimization Problems
Satyen Kale · Chansoo Lee · David Pal

Tue Dec 6th 06:00 -- 09:30 PM @ Area 5+6+7+8 #103 #None

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].

Author Information

Satyen Kale (Google)
Chansoo Lee (Google)
David Pal (Google)

More from the Same Authors