Hardness of Online Sleeping Combinatorial Optimization Problems
Satyen Kale, Chansoo Lee, David Pal
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].
BibTeX
@inproceedings{NIPS2016_18426034,
author = {Kale, Satyen and Lee, Chansoo and Pal, David},
booktitle = {Advances in Neural Information Processing Systems},
editor = {D. Lee and M. Sugiyama and U. Luxburg and I. Guyon and R. Garnett},
pages = {},
publisher = {Curran Associates, Inc.},
title = {Hardness of Online Sleeping Combinatorial Optimization Problems},
url = {https://proceedings.neurips.cc/paper_files/paper/2016/file/184260348236f9554fe9375772ff966e-Paper.pdf},
volume = {29},
year = {2016}
}