Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published 2015 | Published
Book Section - Chapter Open

Smooth Interactive Submodular Set Cover


Interactive submodular set cover is an interactive variant of submodular set cover over a hypothesis class of submodular functions, where the goal is to satisfy all sufficiently plausible submodular functions to a target threshold using as few (cost-weighted) actions as possible. It models settings where there is uncertainty regarding which submodular function to optimize. In this paper, we propose a new extension, which we call smooth interactive submodular set cover, that allows the target threshold to vary depending on the plausibility of each hypothesis. We present the first algorithm for this more general setting with theoretical guarantees on optimality. We further show how to extend our approach to deal with real-valued functions, which yields new theoretical results for real-valued submodular set cover for both the interactive and non-interactive settings.

Additional Information

© 2015 Neural Information Processing Systems.

Attached Files

Published - 6002-smooth-interactive-submodular-set-cover.pdf


Files (832.6 kB)
Name Size Download all
832.6 kB Preview Download

Additional details

August 20, 2023
August 20, 2023