Approximation for maximizing monotone non-decreasing set functions with a greedy method
From MaRDI portal
Recommendations
- Maximizing approximately non-k-submodular monotone set function with matroid constraint
- Monotone approximations of minimum and maximum functions and multi-objective problems
- Approximate solutions in set-valued optimization problems with applications to maximal monotone operators
- An approximation algorithm and its performance guarantee for maximizing non-increasing submodular set function
- A note on monotone approximations of minimum and maximum functions and multi-objective problems
- Continuity and monotonicity of solutions to a greedy maximization problem
- Maximizing a monotone non-submodular function under a knapsack constraint
- Greedy approximation by arbitrary sets
- scientific article; zbMATH DE number 4048460
Cites work
- A note on maximizing a submodular set function subject to a knapsack constraint
- A threshold of ln n for approximating set cover
- An analysis of approximations for maximizing submodular set functions—I
- An Analysis of the Greedy Heuristic for Independence Systems
- An improved approximation algorithm for combinatorial auctions with submodular bidders
- Automata, Languages and Programming
- Best Algorithms for Approximating the Maximum of a Submodular Set Function
- scientific article; zbMATH DE number 5888315 (Why is no real title available?)
- scientific article; zbMATH DE number 3635849 (Why is no real title available?)
- Maximizing a monotone submodular function subject to a matroid constraint
- Maximizing submodular set functions subject to multiple linear constraints
- Non-monotone submodular maximization under matroid and knapsack constraints
- On the approximability of budgeted allocations and improved lower bounds for submodular welfare maximization and GAP
- Optimal approximation for the submodular welfare problem in the value oracle model
- Optimization with demand oracles
- Pipage rounding: a new method of constructing algorithms with proven performance guarantee
- Submodular function maximization via the multilinear relaxation and contention resolution schemes
- Submodular maximization over multiple matroids via generalized exchange properties
- Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
- The submodular welfare problem with demand queries
Cited in
(18)- Exploiting submodularity to quantify near-optimality in multi-agent coverage problems
- Parametric monotone function maximization with matroid constraints
- Two approximation algorithms for maximizing nonnegative weakly monotonic set functions
- A new performance bound for submodular maximization problems and its application to multi-agent optimal coverage problems
- Optimal composition of heterogeneous multi-agent teams for coverage problems with performance bound guarantees
- Submodular optimization problems and greedy strategies: a survey
- Maximize a monotone function with a generic submodularity ratio
- Distributed greedy algorithm for multi-agent task assignment problem with submodular utility functions
- Improved bounds for the greedy strategy in optimization problems with curvature
- A mobile multi-agent sensing problem with submodular functions under a partition matroid
- Performance guarantees of forward and reverse greedy algorithms for minimizing nonsupermodular nonsubmodular functions on a matroid
- Constrained monotone function maximization and the supermodular degree
- A first hitting time approach to finding effective spreaders in a network
- New performance guarantees for the greedy maximization of submodular set functions
- Sequence submodular maximization meets streaming
- Unified greedy approximability beyond submodular maximization
- 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
This page was built for publication: Approximation for maximizing monotone non-decreasing set functions with a greedy method
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5963607)
