Approximation for maximizing monotone non-decreasing set functions with a greedy method
From MaRDI portal
Publication:5963607
DOI10.1007/s10878-014-9707-3zbMath1360.90229OpenAlexW1971161781MaRDI QIDQ5963607
Xuezhi Wang, Zengfu Wang, Quan Pan, William Moran
Publication date: 23 February 2016
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/11343/283251
Related Items (9)
A new performance bound for submodular maximization problems and its application to multi-agent optimal coverage problems ⋮ A mobile multi-agent sensing problem with submodular functions under a partition matroid ⋮ Optimal composition of heterogeneous multi-agent teams for coverage problems with performance bound guarantees ⋮ Submodular optimization problems and greedy strategies: a survey ⋮ Exploiting submodularity to quantify near-optimality in multi-agent coverage problems ⋮ New performance guarantees for the greedy maximization of submodular set functions ⋮ Distributed greedy algorithm for multi-agent task assignment problem with submodular utility functions ⋮ Sequence submodular maximization meets streaming ⋮ A first hitting time approach to finding effective spreaders in a network
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
- A note on maximizing a submodular set function subject to a knapsack constraint
- Pipage rounding: a new method of constructing algorithms with proven performance guarantee
- Optimization with demand oracles
- On the Approximability of Budgeted Allocations and Improved Lower Bounds for Submodular Welfare Maximization and GAP
- A threshold of ln n for approximating set cover
- Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
- An improved approximation algorithm for combinatorial auctions with submodular bidders
- An analysis of approximations for maximizing submodular set functions—I
- An Analysis of the Greedy Heuristic for Independence Systems
- Best Algorithms for Approximating the Maximum of a Submodular Set Function
- Non-monotone submodular maximization under matroid and knapsack constraints
- Submodular function maximization via the multilinear relaxation and contention resolution schemes
- Automata, Languages and Programming
- Submodular Maximization over Multiple Matroids via Generalized Exchange Properties
This page was built for publication: Approximation for maximizing monotone non-decreasing set functions with a greedy method
