Submodular optimization problems and greedy strategies: a survey
From MaRDI portal
Publication:2197586
DOI10.1007/s10626-019-00308-7zbMath1453.90134arXiv1905.03308MaRDI QIDQ2197586
Ali Pezeshki, Edwin K. P. Chong, Zhen-Liang Zhang, Ya-Jing Liu
Publication date: 1 September 2020
Published in: Discrete Event Dynamic Systems (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1905.03308
90C27: Combinatorial optimization
Related Items
Interval dominance based structural results for Markov decision process, A new performance bound for submodular maximization problems and its application to multi-agent optimal coverage problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Maximizing a class of submodular utility functions
- Performance bounds with curvature for batched greedy optimization
- Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
- An efficient approximation for the generalized assignment problem
- An approximation algorithm for the generalized assignment problem
- An inequality for polymatroid functions and its applications.
- A note on maximizing a submodular set function subject to a knapsack constraint
- The budgeted maximum coverage problem
- Improved bounds for the greedy strategy in optimization problems with curvature
- Non-cooperative games
- A Survey of Multi-Objective Sequential Decision-Making
- Solving the Generalized Assignment Problem: An Optimizing and Heuristic Approach
- Online Submodular Welfare Maximization
- String Submodular Functions With Curvature Constraints
- Greedy Adaptive Linear Compression in Signal-Plus-Noise Models
- Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
- Tight approximation algorithms for maximum general assignment problems
- Understanding Cryptography
- Improved Bounds for Matroid Partition and Intersection Algorithms
- Worst case analysis of greedy type algorithms for independence systems
- Maximising Real-Valued Submodular Functions: Primal and Dual Heuristics for Location Problems
- Optimization Strategies in Adaptive Control: A Selective Survey
- P-Complete Approximation Problems
- Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms
- An analysis of approximations for maximizing submodular set functions—I
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Alternative Distributed Algorithms for Network Utility Maximization: Framework and Applications
- Approximate Dynamic Programming
- Submodular Maximization with Cardinality Constraints
- A Unified Continuous Greedy Algorithm for Submodular Maximization
- Transversals and matroid partition
- Online submodular welfare maximization: Greedy is optimal
- Approximation for maximizing monotone non-decreasing set functions with a greedy method