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

DOI10.1016/0166-218X(84)90003-9zbMATH Open0533.90062OpenAlexW2011193572MaRDI QIDQ790044FDOQ790044

Authors: Michele Conforti, Gérard Cornuéjols 

Publication date: 1984

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(84)90003-9

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

zbMATH Keywords

combinatorial optimizationgreedy algorithmmatroidindependence systemsubmodular set functionworst-case bound

Mathematics Subject Classification ID

Integer programming (90C10) Combinatorial aspects of matroids and geometric lattices (05B35)

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
• 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
• Constrained submodular maximization via a nonsymmetric technique
• Deterministic approximation algorithm for submodular maximization subject to a matroid constraint
• Exploiting submodularity to quantify near-optimality in multi-agent coverage problems
• An optimal monotone contention resolution scheme for bipartite matchings via a polyhedral viewpoint
• 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
• When are welfare guarantees robust?
• Distributed greedy algorithm for multi-agent task assignment problem with submodular utility functions
• Valuated matroids: A new look at the greedy algorithm
• Title not available (Why is that?)
• On greedy and submodular matrices
• Tight approximation bounds for maximum multi-coverage
• 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
• Minimizing modular and supermodular functions on \(L\)-matroids
• 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
• An improved analysis of local search for max-sum diversification
• 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
• A ranking model for the greedy algorithm and discrete convexity
• 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?)
• Maximizing a monotone submodular function with a bounded curvature under a knapsack constraint
• 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
• On non-integer submodular set cover problem
• Approximate submodularity and its applications: subset selection, sparse approximation and dictionary selection
• Submodular functions and independence structures
• Maximum coverage problem with group budget constraints
• Combinatorial auctions with decreasing marginal utilities
• Submodular optimization problems and greedy strategies: a survey
• 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
• Hub location as the minimization of a supermodular set function
• 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
• Worst case analysis of greedy and related heuristics for some min-max combinatorial optimization problems
• Recent developments in discrete convex analysis
• Problems on independence systems solvable by the greedy algorithm
• 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
• On the problem of maximizing a modular function in the geometric lattice
• 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
• 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
• Distributed submodular maximization
• 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
• 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

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)