Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem

Recommendations

Approximation for maximizing monotone non-decreasing set functions with a greedy method
scientific article; zbMATH DE number 5888315
Maximizing a monotone submodular function subject to a matroid constraint
Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)
Monotone submodular maximization over a matroid via non-oblivious local search

Cites work

scientific article; zbMATH DE number 3534506 (Why is no real title available?)
scientific article; zbMATH DE number 3544074 (Why is no real title available?)
scientific article; zbMATH DE number 3558962 (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?)
A Greedy Heuristic for the Set-Covering Problem
An Analysis of the Greedy Heuristic for Independence Systems
An analysis of approximations for maximizing submodular set functions—I
Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms
Matroids and the greedy algorithm
On the shortest spanning subtree of a graph and the traveling salesman problem

Cited in

(only showing first 100 items - show all)

Recent developments in discrete convex analysis
Maximizing a non-decreasing non-submodular function subject to various types of constraints
Formulations and Approximation Algorithms for Multilevel Uncapacitated Facility Location
On the geometric structure of independence systems
On greedy and submodular matrices
A new greedy strategy for maximizing monotone submodular function under a cardinality constraint
Online BP functions maximization
Combinatorial auctions with decreasing marginal utilities
An accelerated continuous greedy algorithm for maximizing strong submodular functions
Tight approximation bounds for maximum multi-coverage
scientific article; zbMATH DE number 3854819 (Why is no real title available?)
Worst case analysis of greedy and related heuristics for some min-max combinatorial optimization problems
An optimal monotone contention resolution scheme for bipartite matchings via a polyhedral viewpoint
A generalization of the notion of the rank function of a matroid
Submodular functions and independence structures
Pareto optimization for subset selection with dynamic cost constraints
Submodular optimization problems and greedy strategies: a survey
Graph cuts with interacting edge weights: examples, approximations, and algorithms
Tight approximation bounds for maximum multi-coverage
When are welfare guarantees robust?
Restricted strong convexity implies weak submodularity
Fast algorithms for maximizing monotone nonsubmodular functions
Problems on independence systems solvable by the greedy algorithm
Maximize a monotone function with a generic submodularity ratio
Novel algorithms for maximum DS decomposition
Distributed greedy algorithm for multi-agent task assignment problem with submodular utility functions
A ranking model for the greedy algorithm and discrete convexity
Minimizing modular and supermodular functions on \(L\)-matroids
Quality of local equilibria in discrete exchange economies
A greedy algorithm for convex geometries
ON THE PIPAGE ROUNDING ALGORITHM FOR SUBMODULAR FUNCTION MAXIMIZATION — A VIEW FROM DISCRETE CONVEX ANALYSIS
Maximum coverage problem with group budget constraints
Greedy guarantees for minimum submodular cost submodular/non-submodular cover problem
Informative path planning as a maximum traveling salesman problem with submodular rewards
An improved analysis of local search for max-sum diversification
Deterministic approximation algorithm for submodular maximization subject to a matroid constraint
On Submodular Search and Machine Scheduling
Maximizing a monotone non-submodular function under a knapsack constraint
Constrained submodular maximization via a nonsymmetric technique
Performance bounds with curvature for batched greedy optimization
Online algorithms for BP functions maximization
Submodular Maximization Through the Lens of Linear Programming
On non-integer submodular set cover problem
Hub location as the minimization of a supermodular set function
Performance guarantees of a greedy algorithm for minimizing a supermodular set function on comatroid
Approximate solution of the \(p\)-median minimization problem
Approximation for maximizing monotone non-decreasing set functions with a greedy method
New performance guarantees for the greedy maximization of submodular set functions
Approximate submodularity and its applications: subset selection, sparse approximation and dictionary selection
Maximization problems of balancing submodular relevance and supermodular diversity
Rank axiom of modular supermatroids: a connection with directional DR submodular functions
Valuated matroids: A new look at the greedy algorithm
An adaptive algorithm for maximization of non-submodular function with a matroid constraint
Submodular maximization of concave utility functions composed with a set-union operator with applications to maximal covering location problems
Exploiting submodularity to quantify near-optimality in multi-agent coverage problems
A probabilistic analysis of the maximal covering location problem
Minimum non-submodular cover problem with applications
Parametric monotone function maximization with matroid constraints
scientific article; zbMATH DE number 3867359 (Why is no real title available?)
Maximizing a monotone submodular function with a bounded curvature under a knapsack constraint
Multiple knapsack-constrained monotone DR-submodular maximization on distributive lattice -- continuous greedy algorithm on median complex --
A linear-time streaming algorithm for cardinality-constrained maximizing monotone non-submodular set functions
Improved approximation of maximum vertex cover
Maximizing DR-submodular+supermodular functions on the integer lattice subject to a cardinality constraint
A new performance bound for submodular maximization problems and its application to multi-agent optimal coverage problems
Maximizing expected utility over a knapsack constraint
An approximation guarantee of the greedy descent algorithm for minimzing a supermodular set function.
Analyzing Residual Random Greedy for monotone submodular maximization
Unified greedy approximability beyond submodular maximization
A mobile multi-agent sensing problem with submodular functions under a partition matroid
The regularized submodular maximization via the Lyapunov method
Performance guarantees of forward and reverse greedy algorithms for minimizing nonsupermodular nonsubmodular functions on a matroid
Maximizing stochastic set function under a matroid constraint from decomposition
Streaming algorithms for maximizing the difference of submodular functions and the sum of submodular and supermodular functions
On the problem of maximizing a modular function in the geometric lattice
Greedy is good: constrained non-submodular function maximization via weak submodularity
On stability of the gradient algorithm in convex discrete optimisation problems and related questions
Two-stage submodular maximization under curvature
Two-stage submodular maximization under curvature
A new approximation guarantee for monotone submodular function maximization via discrete convexity
Optimal composition of heterogeneous multi-agent teams for coverage problems with performance bound guarantees
Improved linear-time streaming algorithms for maximizing monotone cardinality-constrained set functions
scientific article; zbMATH DE number 3887436 (Why is no real title available?)
Two-stage non-submodular maximization
Two-stage BP maximization under \(p\)-matroid constraint
Improved bounds for the greedy strategy in optimization problems with curvature
Unified Greedy Approximability beyond Submodular Maximization
Maximization of nonsubmodular functions under multiple constraints with applications
Improved algorithms for non-submodular function maximization problem
Bounds on the Performance of a Greedy Algorithm for Probabilities
An approximation algorithm for the \(\boldsymbol{K}\)-prize-collecting multicut problem in trees with submodular penalties
On the correlation gap of matroids
Minimizing ratio of monotone non-submodular functions
Influence maximization in the presence of vulnerable nodes: a ratio perspective
Distributed submodular maximization
Tight Approximation Bounds for the Seminar Assignment Problem
An exact solution approach for the mobile multi‐agent sensing problem
Two-stage BP maximization under \(p\)-matroid constraint
Optimal experimental design: formulations and computations
Distributed strategy selection: a submodular set function maximization approach

This page was built for publication: Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q790044)