Submodular optimization problems and greedy strategies: a survey
From MaRDI portal
Abstract: The greedy strategy is an approximation algorithm to solve optimization problems arising in decision making with multiple actions. How good is the greedy strategy compared to the optimal solution? In this survey, we mainly consider two classes of optimization problems where the objective function is submodular. The first is set submodular optimization, which is to choose a set of actions to optimize a set submodular objective function, and the second is string submodular optimization, which is to choose an ordered set of actions to optimize a string submodular function. Our emphasis here is on performance bounds for the greedy strategy in submodular optimization problems. Specifically, we review performance bounds for the greedy strategy, more general and improved bounds in terms of curvature, performance bounds for the batched greedy strategy, and performance bounds for Nash equilibria.
Recommendations
- New performance guarantees for the greedy maximization of submodular set functions
- Performance bounds with curvature for batched greedy optimization
- A new greedy strategy for maximizing monotone submodular function under a cardinality constraint
- Greedy guarantees for minimum submodular cost submodular/non-submodular cover problem
- Submodular functions: optimization and approximation
Cites work
- A note on maximizing a submodular set function subject to a knapsack constraint
- A survey of multi-objective sequential decision-making
- A Unified Continuous Greedy Algorithm for Submodular Maximization
- Adaptive submodularity: theory and applications in active learning and stochastic optimization
- Alternative Distributed Algorithms for Network Utility Maximization: Framework and Applications
- An analysis of approximations for maximizing submodular set functions—I
- An approximation algorithm for the generalized assignment problem
- An efficient approximation for the generalized assignment problem
- An inequality for polymatroid functions and its applications.
- Approximate Dynamic Programming
- Approximation for maximizing monotone non-decreasing set functions with a greedy method
- Distributed submodular maximization
- Dynamic programming and optimal control. Vol. 1.
- Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms
- Greedy Adaptive Linear Compression in Signal-Plus-Noise Models
- scientific article; zbMATH DE number 3904328 (Why is no real title available?)
- scientific article; zbMATH DE number 3635849 (Why is no real title available?)
- scientific article; zbMATH DE number 3422402 (Why is no real title available?)
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Improved Bounds for Matroid Partition and Intersection Algorithms
- Improved bounds for the greedy strategy in optimization problems with curvature
- Maximising Real-Valued Submodular Functions: Primal and Dual Heuristics for Location Problems
- Maximizing a class of submodular utility functions
- Maximizing a monotone submodular function subject to a matroid constraint
- Maximizing submodular set functions subject to multiple linear constraints
- Near-optimal sensor placements in Gaussian processes: theory, efficient algorithms and empirical studies
- Non-cooperative games
- Online submodular welfare maximization: greedy beats 1/2 in random order
- Online submodular welfare maximization: greedy is optimal
- Optimal approximation for the submodular welfare problem in the value oracle model
- Optimization Strategies in Adaptive Control: A Selective Survey
- P-Complete Approximation Problems
- Performance bounds with curvature for batched greedy optimization
- Solving the generalized assignment problem: an optimizing and heuristic approach
- String Submodular Functions With Curvature Constraints
- Submodular maximization with cardinality constraints
- Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
- The budgeted maximum coverage problem
- Tight approximation algorithms for maximum general assignment problems
- Transversals and matroid partition
- Understanding Cryptography
- Worst case analysis of greedy type algorithms for independence systems
Cited in
(8)- A refined analysis of submodular greedy
- A new performance bound for submodular maximization problems and its application to multi-agent optimal coverage problems
- Submodular Cost Allocation Problem and Applications
- On the Optimality of the Backward Greedy Algorithm for the Subset Selection Problem
- Bounds on the Performance of a Greedy Algorithm for Probabilities
- Interval dominance based structural results for Markov decision process
- Scalable distributed algorithms for size-constrained submodular maximization in the MapReduce and adaptive complexity models
- Performance bounds with curvature for batched greedy optimization
This page was built for publication: Submodular optimization problems and greedy strategies: a survey
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2197586)
