Deterministic Algorithms for Submodular Maximization Problems
From MaRDI portal
Abstract: Randomization is a fundamental tool used in many theoretical and practical areas of computer science. We study here the role of randomization in the area of submodular function maximization. In this area most algorithms are randomized, and in almost all cases the approximation ratios obtained by current randomized algorithms are superior to the best results obtained by known deterministic algorithms. Derandomization of algorithms for general submodular function maximization seems hard since the access to the function is done via a value oracle. This makes it hard, for example, to apply standard derandomization techniques such as conditional expectations. Therefore, an interesting fundamental problem in this area is whether randomization is inherently necessary for obtaining good approximation ratios. In this work we give evidence that randomization is not necessary for obtaining good algorithms by presenting a new technique for derandomization of algorithms for submodular function maximization. Our high level idea is to maintain explicitly a (small) distribution over the states of the algorithm, and carefully update it using marginal values obtained from an extreme point solution of a suitable linear formulation. We demonstrate our technique on two recent algorithms for unconstrained submodular maximization and for maximizing submodular function subject to a cardinality constraint. In particular, for unconstrained submodular maximization we obtain an optimal deterministic -approximation showing that randomization is unnecessary for obtaining optimal results for this setting.
Recommendations
- Deterministic algorithms for submodular maximization problems
- Deterministic approximation algorithm for submodular maximization subject to a matroid constraint
- Improved deterministic algorithms for non-monotone submodular maximization
- scientific article; zbMATH DE number 3922372
- Exact algorithms for combinatorial optimization problems with submodular objective functions
- Optimum algorithm for maximization of submodular functions
- Approximation guarantees for deterministic maximization of submodular function with a matroid constraint
- Maximization of submodular functions: theory and enumeration algorithms
- On complexity of maximizatin of submodular functions*
- Deterministic (½ + ε)-Approximation for Submodular Maximization over a Matroid
Cited in
(34)- Derandomization for k-submodular maximization
- Non-monotone submodular function maximization under k-system constraint
- Adaptive robust submodular optimization and beyond
- The submodularity of two-stage stochastic maximum-weight independent set problems
- Deterministic algorithms for the hidden subgroup problem
- An optimal monotone contention resolution scheme for bipartite matchings via a polyhedral viewpoint
- Two-stage stochastic max-weight independent set problems
- A 1/2-approximation algorithm for maximizing a non-monotone weak-submodular function on a bounded integer lattice
- Online risk-averse submodular maximization
- Profit maximization in social networks and non-monotone DR-submodular maximization
- A survey on double greedy algorithms for maximizing non-monotone submodular functions
- Deterministic algorithms for submodular maximization problems
- \(k\)-submodular maximization with two kinds of constraints
- Tight approximation for unconstrained XOS maximization
- Generalized assignment via submodular optimization with reserved capacity
- Some Inapproximability Results of MAP Inference and Exponentiated Determinantal Point Processes
- The power of subsampling in submodular maximization
- Stochastic conditional gradient++: (Non)convex minimization and continuous submodular maximization
- Monotone submodular maximization over the bounded integer lattice with cardinality constraints
- A fast double greedy algorithm for non-monotone DR-submodular function maximization
- Deterministic (½ + ε)-Approximation for Submodular Maximization over a Matroid
- Budget-feasible mechanism design for non-monotone submodular objectives: offline and online
- An Optimal Streaming Algorithm for Submodular Maximization with a Cardinality Constraint
- Fast algorithms for maximizing monotone nonsubmodular functions
- Improved deterministic algorithms for non-monotone submodular maximization
- A binary search double greedy algorithm for non-monotone DR-submodular maximization
- Improved deterministic algorithms for non-monotone submodular maximization
- Deterministic \(\boldsymbol{(\unicode{x00BD}+\varepsilon)}\) -Approximation for Submodular Maximization over a Matroid
- On the cut-query complexity of approximating max-cut
- Separating coverage and submodular: maximization subject to a cardinality constraint
- Revisiting non-monotone regularized submodular maximization: bi-criteria and pass approximations
- Efficient deterministic algorithms for maximizing symmetric submodular functions
- Deterministic algorithms for multi-criteria max-TSP
- Approximation algorithms for multi-market competitive facility location problem with endogenous demand and diminishing marginal effect
This page was built for publication: Deterministic Algorithms for Submodular Maximization Problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4554360)
