Scenario submodular cover

DOI10.1007/978-3-319-51741-4_10MaRDI QIDQ2971162zbMATH OpenOpenAlexFDO

Authors Nathaniel Grammel, Devorah Kletenik, Patrick Lin, Lisa Hellerstein

Publication date 4 April 2017

Published in Approximation and Online Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1603.03158

Mathematics Subject Classification ID

Approximation algorithms (68W25) Stochastic programming (90C15) Approximation methods and heuristics in mathematical programming (90C59)

Abstract: Many problems in Machine Learning can be modeled as submodular optimization problems. Recent work has focused on stochastic or adaptive versions of these problems. We consider the Scenario Submodular Cover problem, which is a counterpart to the Stochastic Submodular Cover problem studied by Golovin and Krause. In Scenario Submodular Cover, the goal is to produce a cover with minimum expected cost, where the expectation is with respect to an empirical joint distribution, given as input by a weighted sample of realizations. In contrast, in Stochastic Submodular Cover, the variables of the input distribution are assumed to be independent, and the distribution of each variable is given as input. Building on algorithms developed by Cicalese et al. and Golovin and Krause for related problems, we give two approximation algorithms for Scenario Submodular Cover over discrete distributions. The first achieves an approximation factor of O(log Qm), where m is the size of the sample and Q is the goal utility. The second, simpler algorithm achieves an approximation bound of O(log QW), where Q is the goal utility and W is the sum of the integer weights. (Both bounds assume an integer-valued utility function.) Our results yield approximation bounds for other problems involving non-independent distributions that are explicitly specified by their support.

Recommendations

• Approximation algorithms for stochastic submodular set cover with applications to Boolean function evaluation and min-knapsack
• Approximation algorithms for stochastic Boolean function evaluation and stochastic submodular set cover
• Adaptive submodular ranking
• Stochastic submodular cover with limited adaptivity

Cites work

• Adaptive submodular ranking
• Adaptive submodularity: theory and applications in active learning and stochastic optimization
• Approximation Algorithms for Optimal Decision Trees and Adaptive TSP Problems
• Approximation algorithms for stochastic submodular set cover with applications to Boolean function evaluation and min-knapsack
• Group-Based Active Query Selection for Rapid Diagnosis in Time-Critical Situations
• scientific article; zbMATH DE number 2185610 (Why is no real title available?)
• Learning with attribute costs
• Maximising Real-Valued Submodular Functions: Primal and Dual Heuristics for Location Problems
• Scenario submodular cover
• Sequential testing of complex systems: a review

Cited in

(8)

• Scenario submodular cover
• Approximation algorithms for stochastic submodular set cover with applications to Boolean function evaluation and min-knapsack
• Revisiting the approximation bound for stochastic submodular cover
• The stochastic score classification problem
• Adaptive submodular ranking and routing
• Approximation algorithms for stochastic k-TSP
• Approximation algorithms for stochastic Boolean function evaluation and stochastic submodular set cover
• Applied Cryptography and Network Security

This page was built for publication: Scenario submodular cover

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2971162)