Submodular Cost Submodular Cover with an Approximate Oracle

Victoria Crawford, Alan Kuhnle, My Thai
Proceedings of the 36th International Conference on Machine Learning, PMLR 97:1426-1435, 2019.

Abstract

In this work, we study the Submodular Cost Submodular Cover problem, which is to minimize the submodular cost required to ensure that the submodular benefit function exceeds a given threshold. Existing approximation ratios for the greedy algorithm assume a value oracle to the benefit function. However, access to a value oracle is not a realistic assumption for many applications of this problem, where the benefit function is difficult to compute. We present two incomparable approximation ratios for this problem with an approximate value oracle and demonstrate that the ratios take on empirically relevant values through a case study with the Influence Threshold problem in online social networks.

Cite this Paper

BibTeX
@InProceedings{pmlr-v97-crawford19a, title = {Submodular Cost Submodular Cover with an Approximate Oracle}, author = {Crawford, Victoria and Kuhnle, Alan and Thai, My}, booktitle = {Proceedings of the 36th International Conference on Machine Learning}, pages = {1426--1435}, year = {2019}, editor = {Chaudhuri, Kamalika and Salakhutdinov, Ruslan}, volume = {97}, series = {Proceedings of Machine Learning Research}, month = {09--15 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v97/crawford19a/crawford19a.pdf}, url = {https://proceedings.mlr.press/v97/crawford19a.html}, abstract = {In this work, we study the Submodular Cost Submodular Cover problem, which is to minimize the submodular cost required to ensure that the submodular benefit function exceeds a given threshold. Existing approximation ratios for the greedy algorithm assume a value oracle to the benefit function. However, access to a value oracle is not a realistic assumption for many applications of this problem, where the benefit function is difficult to compute. We present two incomparable approximation ratios for this problem with an approximate value oracle and demonstrate that the ratios take on empirically relevant values through a case study with the Influence Threshold problem in online social networks.} }
Endnote
%0 Conference Paper %T Submodular Cost Submodular Cover with an Approximate Oracle %A Victoria Crawford %A Alan Kuhnle %A My Thai %B Proceedings of the 36th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Ruslan Salakhutdinov %F pmlr-v97-crawford19a %I PMLR %P 1426--1435 %U https://proceedings.mlr.press/v97/crawford19a.html %V 97 %X In this work, we study the Submodular Cost Submodular Cover problem, which is to minimize the submodular cost required to ensure that the submodular benefit function exceeds a given threshold. Existing approximation ratios for the greedy algorithm assume a value oracle to the benefit function. However, access to a value oracle is not a realistic assumption for many applications of this problem, where the benefit function is difficult to compute. We present two incomparable approximation ratios for this problem with an approximate value oracle and demonstrate that the ratios take on empirically relevant values through a case study with the Influence Threshold problem in online social networks.
APA
Crawford, V., Kuhnle, A. & Thai, M.. (2019). Submodular Cost Submodular Cover with an Approximate Oracle. Proceedings of the 36th International Conference on Machine Learning, in Proceedings of Machine Learning Research 97:1426-1435 Available from https://proceedings.mlr.press/v97/crawford19a.html.

Related Material