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

Cites Work

On the shortest spanning subtree of a graph and the traveling salesman problem
Title not available (Why is that?)
Title not available (Why is that?)
A Greedy Heuristic for the Set-Covering Problem
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
An analysis of approximations for maximizing submodular set functions—I
An Analysis of the Greedy Heuristic for Independence Systems
Matroids and the greedy algorithm
Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms

Cited In (only showing first 100 items - show all)

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
Hub Location as the Minimization of a Supermodular Set Function
An Improved Analysis of Local Search for Max-Sum Diversification
Approximation for maximizing monotone non-decreasing set functions with a greedy method
Restricted strong convexity implies weak submodularity
ON THE PIPAGE ROUNDING ALGORITHM FOR SUBMODULAR FUNCTION MAXIMIZATION — A VIEW FROM DISCRETE CONVEX ANALYSIS
Deterministic approximation algorithm for submodular maximization subject to a matroid constraint
Exploiting submodularity to quantify near-optimality in multi-agent coverage problems
Recent Developments in Discrete Convex Analysis
An optimal monotone contention resolution scheme for bipartite matchings via a polyhedral viewpoint
Title not available (Why is that?)
Maximizing a Monotone Submodular Function with a Bounded Curvature under a Knapsack Constraint
Maximizing expected utility over a knapsack constraint
Pareto optimization for subset selection with dynamic cost constraints
Parametric monotone function maximization with matroid constraints
Maximizing a non-decreasing non-submodular function subject to various types of constraints
Title not available (Why is that?)
Distributed greedy algorithm for multi-agent task assignment problem with submodular utility functions
Title not available (Why is that?)
Tight approximation bounds for maximum multi-coverage
Performance bounds with curvature for batched greedy optimization
A generalization of the notion of the rank function of a matroid
Novel algorithms for maximum DS decomposition
A greedy algorithm for convex geometries
Maximizing a monotone non-submodular function under a knapsack constraint
A new greedy strategy for maximizing monotone submodular function under a cardinality constraint
Quality of local equilibria in discrete exchange economies
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
Unified greedy approximability beyond submodular maximization
Greedy guarantees for minimum submodular cost submodular/non-submodular cover problem
An accelerated continuous greedy algorithm for maximizing strong submodular functions
Graph cuts with interacting edge weights: examples, approximations, and algorithms
Minimum non-submodular cover problem with applications
Online BP functions maximization
Title not available (Why is that?)
Online algorithms for BP functions maximization
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
On the geometric structure of independence systems
Optimal composition of heterogeneous multi-agent teams for coverage problems with performance bound guarantees
Submodular functions and independence structures
Improved bounds for the greedy strategy in optimization problems with curvature
FPT approximation schemes for maximizing submodular functions
Maximum coverage problem with group budget constraints
Combinatorial auctions with decreasing marginal utilities
Submodular optimization problems and greedy strategies: a survey
Constrained Submodular Maximization via a Nonsymmetric Technique
Maximization problems of balancing submodular relevance and supermodular diversity
Rank axiom of modular supermatroids: a connection with directional DR submodular functions
Submodular Maximization Through the Lens of Linear Programming
Maximize a monotone function with a generic submodularity ratio
An approximation guarantee of the greedy descent algorithm for minimzing a supermodular set function.
Fast algorithms for maximizing monotone nonsubmodular functions
Analyzing Residual Random Greedy for monotone submodular maximization
Tight Approximation Bounds for Maximum Multi-coverage
When Are Welfare Guarantees Robust
Worst case analysis of greedy and related heuristics for some min-max combinatorial optimization problems
Approximate solution of the \(p\)-median minimization problem
Formulations and Approximation Algorithms for Multilevel Uncapacitated Facility Location
A probabilistic analysis of the maximal covering location problem
Informative path planning as a maximum traveling salesman problem with submodular rewards
On Submodular Search and Machine Scheduling
Performance guarantees of a greedy algorithm for minimizing a supermodular set function on comatroid
New performance guarantees for the greedy maximization of submodular set functions
Improved approximation of maximum vertex cover
Improved algorithms for non-submodular function maximization problem
Fast deterministic algorithms for non-submodular maximization with strong performance guarantees
Greedy is good: constrained non-submodular function maximization via weak submodularity
Unified Greedy Approximability beyond Submodular Maximization
Influence maximization in the presence of vulnerable nodes: a ratio perspective
Minimizing ratio of monotone non-submodular functions
Two-stage submodular maximization under curvature
Two-stage submodular maximization under curvature
Title not available (Why is that?)
The regularized submodular maximization via the Lyapunov method
Streaming algorithms for maximizing the difference of submodular functions and the sum of submodular and supermodular functions
Title not available (Why is that?)
Optimal experimental design: formulations and computations
Distributed strategy selection: a submodular set function maximization approach
Title not available (Why is that?)
Tight Approximation Bounds for the Seminar Assignment Problem
Improved linear-time streaming algorithms for maximizing monotone cardinality-constrained set functions
An approximation algorithm for the \(\boldsymbol{K}\)-prize-collecting multicut problem in trees with submodular penalties
Bounds on the Performance of a Greedy Algorithm for Probabilities
Maximizing stochastic set function under a matroid constraint from decomposition
An exact solution approach for the mobile multi‐agent sensing problem
Two-stage BP maximization under \(p\)-matroid constraint
Parallelized maximization of nonsubmodular function subject to a cardinality constraint
Improved algorithms for non-submodular function maximization problem
Sequence submodular maximization meets streaming
Parallelized maximization of nonsubmodular function subject to a cardinality constraint
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
Maximization of nonsubmodular functions under multiple constraints with applications
Two-stage non-submodular maximization
Two-stage BP maximization under \(p\)-matroid constraint
Greedy guarantees for non-submodular function maximization under independent system constraint with applications
A single factor approximation ratio algorithm for DR-submodular maximization on integer lattice beyond non-negativity and monotonicity

   Recommendations

Approximation for maximizing monotone non-decreasing set functions with a greedy method 👍 👎
Title not available (Why is that?) 👍 👎
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 👍 👎

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)