Submodular Approximation: Sampling-based Algorithms and Lower Bounds
From MaRDI portal
Publication:3225170
Abstract: We introduce several generalizations of classical computer science problems obtained by replacing simpler objective functions with general submodular functions. The new problems include submodular load balancing, which generalizes load balancing or minimum-makespan scheduling, submodular sparsest cut and submodular balanced cut, which generalize their respective graph cut problems, as well as submodular function minimization with a cardinality lower bound. We establish upper and lower bounds for the approximability of these problems with a polynomial number of queries to a function-value oracle. The approximation guarantees for most of our algorithms are of the order of sqrt(n/ln n). We show that this is the inherent difficulty of the problems by proving matching lower bounds. We also give an improved lower bound for the problem of approximately learning a monotone submodular function. In addition, we present an algorithm for approximately learning submodular functions with special structure, whose guarantee is close to the lower bound. Although quite restrictive, the class of functions with this structure includes the ones that are used for lower bounds both by us and in previous work. This demonstrates that if there are significantly stronger lower bounds for this problem, they rely on more general submodular functions.
Recommendations
- The power of subsampling in submodular maximization
- Sampling subproblems of heterogeneous Max-Cut problems and approximation algorithms
- STACS 2005
- Algorithms and lower bounds for submodular cuts and approximating submodular functions
- Revisiting the approximation bound for stochastic submodular cover
- scientific article; zbMATH DE number 7051222
- Sublinear‐time approximation algorithms for clustering via random sampling
- Submodular maximization with nearly optimal approximation, adaptivity and query complexity
- Sampling algorithms: lower bounds and applications
- On approximation of the submodular set cover problem
Cited in
(46)- Polyhedral results for a class of cardinality constrained submodular minimization problems
- Robust budget allocation via continuous submodular functions
- Optimizing network topology for average controllability
- An exact cutting plane method for k-submodular function maximization
- New approximations and hardness results for submodular partitioning problems
- Multi-attribute based influence maximization in social networks: algorithms and analysis
- Influence maximization in the presence of vulnerable nodes: a ratio perspective
- Set function optimization
- Multi-dimensional vector assignment problems
- Activity preserving graph simplification
- A polyhedral approach to bisubmodular function minimization
- Combinatorial optimization. Abstracts from the workshop held November 7--13, 2021 (hybrid meeting)
- Exact Sublinear Binomial Sampling
- Hardness of submodular cost allocation: lattice matching and a simplex coloring conjecture
- Algorithms and lower bounds for submodular cuts and approximating submodular functions
- Submodular function minimization under a submodular set covering constraint
- Nonmonotone submodular maximization via a structural continuous greedy algorithm (extended abstract)
- Submodular Cost Allocation Problem and Applications
- Submodular Max-SAT
- A tight linear time (1/2)-approximation for unconstrained submodular maximization
- The Submodular Facility Location Problem and the Submodular Joint Replenishment Problem
- The Methods for Approximation of Principal Points for Binary Distributions on the Basis of Submodularity
- Sampling subproblems of heterogeneous Max-Cut problems and approximation algorithms
- Submodular functions: learnability, structure, and optimization
- Multi-agent submodular optimization
- Graph cuts with interacting edge weights: examples, approximations, and algorithms
- Bottom-k and priority sampling, set similarity and subset sums with minimal independence
- scientific article; zbMATH DE number 7651150 (Why is no real title available?)
- Exact sublinear binomial sampling
- Algorithms for maximizing monotone submodular function minus modular function under noise
- Efficient and Near-optimal Algorithms for Sampling Small Connected Subgraphs
- Approximating Nash Social Welfare under Submodular Valuations through (Un)Matchings
- Strong valid inequalities for a class of concave submodular minimization problems under cardinality constraints
- Using atomic bounds to get sub-modular approximations
- Minimization problems with non-submodular cover constraint
- Linearly representable submodular functions: an algebraic algorithm for minimization
- Approximation algorithms for two extensions of min-k-union
- The ground-set-cost budgeted maximum coverage problem
- Global approximation of local optimality: nonsubmodular optimization
- On extensions of min-k-union
- Shortest cycles with monotone submodular costs
- Submodular combinatorial information measures with applications in machine learning
- A note on submodular function minimization with covering type linear constraints
- Scheduling on identical machines with setup time and unknown execution time
- Submodular hypergraph partitioning: metric relaxations and fast algorithms via an improved cut-matching game
- A spatial branch-and-bound approach for maximization of differentiable monotone continuous submodular functions
This page was built for publication: Submodular Approximation: Sampling-based Algorithms and Lower Bounds
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3225170)
