Submodular Optimization with Submodular Cover and Submodular Knapsack Constraints
arXiv:1311.2106
Abstract
We investigate two new optimization problems -- minimizing a submodular function subject to a submodular lower bound constraint (submodular cover) and maximizing a submodular function subject to a submodular upper bound constraint (submodular knapsack). We are motivated by a number of real-world applications in machine learning including sensor placement and data subset selection, which require maximizing a certain submodular function (like coverage or diversity) while simultaneously minimizing another (like cooperative cost). These problems are often posed as minimizing the difference between submodular functions [14, 35] which is in the worst case inapproximable. We show, however, that by phrasing these problems as constrained optimization, which is more natural for many applications, we achieve a number of bounded approximation guarantees. We also show that both these problems are closely related and an approximation algorithm solving one can be used to obtain an approximation guarantee for the other. We provide hardness results for both problems thus showing that our approximation factors are tight up to log-factors. Finally, we empirically demonstrate the performance and good scalability properties of our algorithms.
23 pages. A short version of this appeared in Advances of NIPS-2013
References in corpus (3)
Cited by in corpus (25)
- Maximization of Approximately Submodular Functions
- Pareto Optimization for Subset Selection with Dynamic Cost Constraints
- Curvature and Optimal Algorithms for Learning and Minimizing Submodular Functions
- Sparse Sampling for Inverse Problems with Tensors
- Provable Submodular Minimization using Wolfe's Algorithm
- Submodular Combinatorial Information Measures with Applications in Machine Learning
- Network Support for High-performance Distributed Machine Learning
- Stochastic Submodular Maximization: The Case of Coverage Functions
- Discrepancy-Based Active Learning for Domain Adaptation
- Neural Network Architecture Optimization through Submodularity and Supermodularity
- Shifting Opinions in a Social Network Through Leader Selection
- Quantum and Classical Algorithms for Approximate Submodular Function Minimization
- Contextual Centrality: Going Beyond Network Structures
- Adaptive Information Gathering via Imitation Learning
- Learning to Gather Information via Imitation
- Sensitivity Analysis of Submodular Function Maximization
- Variational Optimization for the Submodular Maximum Coverage Problem
- Tiering as a Stochastic Submodular Optimization Problem
- Parallel Quasi-concave set optimization: A new frontier that scales without needing submodularity
- Efficient and Effective Algorithms for Revenue Maximization in Social Advertising
- The Power of Randomization: Efficient and Effective Algorithms for Constrained Submodular Maximization
- Fast Parallel Algorithms for Submodular -Superseparable Maximization
- Bounding Inefficiency of Equilibria in Continuous Actions Games using Submodularity and Curvature
- Subquadratic Submodular Function Minimization
- Submodular Maximization using Test Scores