Best Algorithms for Approximating the Maximum of a Submodular Set Function
From MaRDI portal
Publication:4178796
DOI10.1287/moor.3.3.177zbMath0395.90072MaRDI 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
Combinatorial Optimization; Computational Efficiency; Greedy Algorithms; Best Algorithms; Partial Enumeration; Submodular Set Function
68Q25: Analysis of algorithms and problem complexity
65K05: Numerical mathematical programming methods
90C30: Nonlinear programming
05C30: Enumeration in graph theory
Related Items
Unnamed Item, Unnamed Item, A first hitting time approach to finding effective spreaders in a network, Online Submodular Maximization with Preemption, Non-Submodular Maximization with Matroid and Knapsack Constraints, Tight Approximation for Unconstrained XOS Maximization, Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model, 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, Monotone submodular maximization over the bounded integer lattice with cardinality constraints, A fast double greedy algorithm for non-monotone DR-submodular function maximization, Approximation for maximizing monotone non-decreasing set functions with a greedy method, Fast algorithms for maximizing monotone nonsubmodular functions, Guess free maximization of submodular and linear sums, New performance guarantees for the greedy maximization of submodular set functions, Some comments on the Slater number, Maximizing a class of submodular utility functions, Sensor networks: from dependence analysis via matroid bases to online synthesis, Computational results from a new Lagrangean relaxation algorithm for the capacitated plant location problem, The leader-follower location model, An accelerated continuous greedy algorithm for maximizing strong submodular functions, Submodular maximization meets streaming: matchings, matroids, and more, Maximization of submodular functions: theory and enumeration algorithms, Local optimization on graphs, Lower bounds on the worst-case complexity of some oracle algorithms, An approximation algorithm for a competitive facility location problem with network effects, Robust monotone submodular function maximization, Dividing and conquering the square, The simple plant location problem: Survey and synthesis, An optimization approach to plan for reusable software components, Greedy heuristics for single-machine scheduling problems with general earliness and tardiness costs, A note on solving DiDi's driver-order matching problem, Learning diffusion on global graph: a PDE-directed approach for feature detection on geometric shapes, Maximizing DR-submodular+supermodular functions on the integer lattice subject to a cardinality constraint, A refined analysis of submodular greedy, An almost optimal approximation algorithm for monotone submodular multiple knapsack, Adaptive seeding for profit maximization in social networks, An optimal monotone contention resolution scheme for bipartite matchings via a polyhedral viewpoint, Siting renewable power generation assets with combinatorial optimisation, Maximize a monotone function with a generic submodularity ratio, Deterministic approximation algorithm for submodular maximization subject to a matroid constraint, Viral marketing of online game by DS decomposition in social networks, Constrained submodular maximization via greedy local search, Maximizing submodular or monotone approximately submodular functions by multi-objective evolutionary algorithms, Minimizing ratio of monotone non-submodular functions, Optimization with demand oracles, Bulk-robust combinatorial optimization, The matroid intersection cover problem, Stochastic-lazier-greedy algorithm for monotone non-submodular maximization, Unnamed Item, Hub Location as the Minimization of a Supermodular Set Function, Bounds on Double-Sided Myopic Algorithms for Unconstrained Non-monotoneSubmodular Maximization, Discrete Stochastic Submodular Maximization: Adaptive vs. Non-adaptive vs. Offline, A Probabilistic Analysis of the K-Location Problem, Robust Monotone Submodular Function Maximization, Submodular Stochastic Probing on Matroids, Gradient methods of maximization of convex functions on discrete structures, A Canonical Representation of Simple Plant Location Problems and Its Applications, Maximizing set function formulation of two scheduling problems, NP-Complete operations research problems and approximation algorithms
