Best Algorithms for Approximating the Maximum of a Submodular Set Function

DOI10.1287/moor.3.3.177zbMath0395.90072OpenAlexW1997783781MaRDI QIDQ4178796

Nemhauser, George I., Laurence A. Wolsey

Publication date: 1978

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/moor.3.3.177

zbMATH Keywords

Combinatorial OptimizationComputational EfficiencyGreedy AlgorithmsBest AlgorithmsPartial EnumerationSubmodular Set Function

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Nonlinear programming (90C30) Enumeration in graph theory (05C30)

Related Items (96)

Siting renewable power generation assets with combinatorial optimisation ⋮ A Canonical Representation of Simple Plant Location Problems and Its Applications ⋮ Greedy heuristics for single-machine scheduling problems with general earliness and tardiness costs ⋮ An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model ⋮ Ranking with submodular functions on a budget ⋮ Bi-criteria adaptive algorithms for minimizing supermodular functions with cardinality constraint ⋮ Measured continuous greedy with differential privacy ⋮ Robust Monotone Submodular Function Maximization ⋮ Submodular Stochastic Probing on Matroids ⋮ Maximizing a non-decreasing non-submodular function subject to various types of constraints ⋮ Gradient methods of maximization of convex functions on discrete structures ⋮ Hub Location as the Minimization of a Supermodular Set Function ⋮ The Power of Subsampling in Submodular Maximization ⋮ The matroid intersection cover problem ⋮ Local optimization on graphs ⋮ Maximizing set function formulation of two scheduling problems ⋮ Stochastic-lazier-greedy algorithm for monotone non-submodular maximization ⋮ Bounds on Double-Sided Myopic Algorithms for Unconstrained Non-monotoneSubmodular Maximization ⋮ The leader-follower location model ⋮ Discrete Stochastic Submodular Maximization: Adaptive vs. Non-adaptive vs. Offline ⋮ Optimization with demand oracles ⋮ An accelerated continuous greedy algorithm for maximizing strong submodular functions ⋮ An optimal streaming algorithm for non-submodular functions maximization on the integer lattice ⋮ A fast and deterministic algorithm for knapsack-constrained monotone DR-submodular maximization over an integer lattice ⋮ Analyzing Residual Random Greedy for monotone submodular maximization ⋮ Evolutionary algorithms and submodular functions: benefits of heavy-tailed mutations ⋮ Multi-objective evolutionary algorithms are generally good: maximizing monotone submodular functions over sequences ⋮ FPT-Algorithms for the \(\ell\) -Matchoid Problem with a Coverage Objective ⋮ Submodular maximization meets streaming: matchings, matroids, and more ⋮ Distributed strategy selection: a submodular set function maximization approach ⋮ Constrained Submodular Maximization via a Nonsymmetric Technique ⋮ Submodular Maximization Through the Lens of Linear Programming ⋮ An Improved Analysis of Local Search for Max-Sum Diversification ⋮ Streaming submodular maximization under \(d\)-knapsack constraints ⋮ Unnamed Item ⋮ On maximizing sums of non-monotone submodular and linear functions ⋮ Improved deterministic algorithms for non-monotone submodular maximization ⋮ Algorithms for cardinality-constrained monotone DR-submodular maximization with low adaptivity and query complexity ⋮ Improved deterministic algorithms for non-monotone submodular maximization ⋮ Streaming submodular maximization with the chance constraint ⋮ Deterministic \(\boldsymbol{(\unicode{x00BD}+\varepsilon)}\) -Approximation for Submodular Maximization over a Matroid ⋮ Unnamed Item ⋮ Practical budgeted submodular maximization ⋮ Maximize a monotone function with a generic submodularity ratio ⋮ A (1-e^{-1}-ε)-Approximation for the Monotone Submodular Multiple Knapsack Problem ⋮ Deterministic approximation algorithm for submodular maximization subject to a matroid constraint ⋮ Unnamed Item ⋮ New performance guarantees for the greedy maximization of submodular set functions ⋮ An approximation algorithm for a competitive facility location problem with network effects ⋮ A note on solving DiDi's driver-order matching problem ⋮ Some comments on the Slater number ⋮ Evaluation of Combinatorial Optimisation Algorithms for c-Optimal Experimental Designs with Correlated Observations ⋮ Maximizing a class of submodular utility functions ⋮ Learning diffusion on global graph: a PDE-directed approach for feature detection on geometric shapes ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Viral marketing of online game by DS decomposition in social networks ⋮ Approximation for maximizing monotone non-decreasing set functions with a greedy method ⋮ Bulk-robust combinatorial optimization ⋮ Lower bounds on the worst-case complexity of some oracle algorithms ⋮ Monotone submodular maximization over the bounded integer lattice with cardinality constraints ⋮ Fast algorithms for maximizing monotone nonsubmodular functions ⋮ Fast algorithms for maximizing monotone nonsubmodular functions ⋮ Approximation guarantees for parallelized maximization of monotone non-submodular function with a cardinality constraint ⋮ Robust monotone submodular function maximization ⋮ Dividing and conquering the square ⋮ Constrained submodular maximization via greedy local search ⋮ Maximizing DR-submodular+supermodular functions on the integer lattice subject to a cardinality constraint ⋮ Sensor networks: from dependence analysis via matroid bases to online synthesis ⋮ A first hitting time approach to finding effective spreaders in a network ⋮ A fast double greedy algorithm for non-monotone DR-submodular function maximization ⋮ Guess free maximization of submodular and linear sums ⋮ Online Submodular Maximization with Preemption ⋮ NP-Complete operations research problems and approximation algorithms ⋮ A refined analysis of submodular greedy ⋮ A Tight Approximation for Submodular Maximization with Mixed Packing and Covering Constraints ⋮ Maximization of submodular functions: theory and enumeration algorithms ⋮ An almost optimal approximation algorithm for monotone submodular multiple knapsack ⋮ Maximizing submodular or monotone approximately submodular functions by multi-objective evolutionary algorithms ⋮ Minimizing ratio of monotone non-submodular functions ⋮ The simple plant location problem: Survey and synthesis ⋮ Private non-monotone submodular maximization ⋮ An optimization approach to plan for reusable software components ⋮ An adaptive algorithm for maximization of non-submodular function with a matroid constraint ⋮ Submodular function minimization and polarity ⋮ A Probabilistic Analysis of the K-Location Problem ⋮ Unnamed Item ⋮ An Optimal Streaming Algorithm for Submodular Maximization with a Cardinality Constraint ⋮ Non-Submodular Maximization with Matroid and Knapsack Constraints ⋮ Computational results from a new Lagrangean relaxation algorithm for the capacitated plant location problem ⋮ Tight Approximation for Unconstrained XOS Maximization ⋮ Adaptive seeding for profit maximization in social networks ⋮ Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model ⋮ An optimal monotone contention resolution scheme for bipartite matchings via a polyhedral viewpoint

This page was built for publication: Best Algorithms for Approximating the Maximum of a Submodular Set Function