Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
From MaRDI portal
Publication:790044
DOI10.1016/0166-218X(84)90003-9zbMath0533.90062OpenAlexW2011193572MaRDI QIDQ790044
Michele Conforti, Cornuéjols, Gérard
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
combinatorial optimizationgreedy algorithmmatroidindependence systemsubmodular set functionworst-case bound
Related Items
Tight Approximation Bounds for Maximum Multi-coverage, A new greedy strategy for maximizing monotone submodular function under a cardinality 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, Maximizing a non-decreasing non-submodular function subject to various types of constraints, Maximizing a monotone non-submodular function under a knapsack constraint, A new performance bound for submodular maximization problems and its application to multi-agent optimal coverage problems, Hub Location as the Minimization of a Supermodular Set Function, Quality of local equilibria in discrete exchange economies, 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, Maximum coverage problem with group budget constraints, FPT approximation schemes for maximizing submodular functions, Optimal composition of heterogeneous multi-agent teams for coverage problems with performance bound guarantees, On stability of the gradient algorithm in convex discrete optimisation problems and related questions, Analyzing Residual Random Greedy for monotone submodular maximization, Maximization of nonsubmodular functions under multiple constraints with applications, Distributed strategy selection: a submodular set function maximization approach, Two-stage non-submodular maximization, Two-stage BP maximization under \(p\)-matroid constraint, Constrained Submodular Maximization via a Nonsymmetric Technique, Submodular Maximization Through the Lens of Linear Programming, On Submodular Search and Machine Scheduling, An Improved Analysis of Local Search for Max-Sum Diversification, A single factor approximation ratio algorithm for DR-submodular maximization on integer lattice beyond non-negativity and monotonicity, Improved bounds for the greedy strategy in optimization problems with curvature, Two-stage non-submodular maximization, Unified Greedy Approximability beyond Submodular Maximization, Streaming algorithms for maximizing the difference of submodular functions and the sum of submodular and supermodular functions, Submodular optimization problems and greedy strategies: a survey, Unified greedy approximability beyond submodular maximization, Unnamed Item, Two-stage BP maximization under \(p\)-matroid constraint, An exact solution approach for the mobile multi‐agent sensing problem, Tight Approximation Bounds for the Seminar Assignment Problem, Greedy guarantees for non-submodular function maximization under independent system constraint with applications, Recent Developments in Discrete Convex Analysis, Formulations and Approximation Algorithms for Multilevel Uncapacitated Facility Location, Influence maximization in the presence of vulnerable nodes: a ratio perspective, Maximize a monotone function with a generic submodularity ratio, Online algorithms for BP functions maximization, When Are Welfare Guarantees Robust, Exploiting submodularity to quantify near-optimality in multi-agent coverage problems, Deterministic approximation algorithm for submodular maximization subject to a matroid constraint, Unnamed Item, Restricted strong convexity implies weak submodularity, Minimum non-submodular cover problem with applications, Graph cuts with interacting edge weights: examples, approximations, and algorithms, Approximate solution of the \(p\)-median minimization problem, New performance guarantees for the greedy maximization of submodular set functions, Parametric monotone function maximization with matroid constraints, Unnamed Item, An approximation guarantee of the greedy descent algorithm for minimzing a supermodular set function., Maximizing expected utility over a knapsack constraint, Combinatorial auctions with decreasing marginal utilities, Distributed greedy algorithm for multi-agent task assignment problem with submodular utility functions, Performance bounds with curvature for batched greedy optimization, Approximation for maximizing monotone non-decreasing set functions with a greedy method, Online BP functions maximization, Parallelized maximization of nonsubmodular function subject to a cardinality constraint, Sequence submodular maximization meets streaming, Fast algorithms for maximizing monotone nonsubmodular functions, A probabilistic analysis of the maximal covering location problem, Two-stage submodular maximization under curvature, Improved algorithms for non-submodular function maximization problem, Maximizing DR-submodular+supermodular functions on the integer lattice subject to a cardinality constraint, Parallelized maximization of nonsubmodular function subject to a cardinality constraint, Novel algorithms for maximum DS decomposition, Two-stage submodular maximization under curvature, ON THE PIPAGE ROUNDING ALGORITHM FOR SUBMODULAR FUNCTION MAXIMIZATION — A VIEW FROM DISCRETE CONVEX ANALYSIS, Pareto optimization for subset selection with dynamic cost constraints, Maximizing a Monotone Submodular Function with a Bounded Curvature under a Knapsack Constraint, On the geometric structure of independence systems, Rank axiom of modular supermatroids: a connection with directional DR submodular functions, Maximization problems of balancing submodular relevance and supermodular diversity, Minimizing ratio of monotone non-submodular functions, 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, Greedy guarantees for minimum submodular cost submodular/non-submodular cover problem, Improved algorithms for non-submodular function maximization problem, Improved approximation of maximum vertex cover, Informative path planning as a maximum traveling salesman problem with submodular rewards, Unnamed Item, An optimal monotone contention resolution scheme for bipartite matchings via a polyhedral viewpoint, Tight approximation bounds for maximum multi-coverage, Performance guarantees of a greedy algorithm for minimizing a supermodular set function on comatroid
Cites Work
- On the shortest spanning subtree of a graph and the traveling salesman problem
- A Greedy Heuristic for the Set-Covering Problem
- Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms
- An analysis of approximations for maximizing submodular set functions—I
- An Analysis of the Greedy Heuristic for Independence Systems
- Matroids and the greedy algorithm
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
