Best Algorithms for Approximating the Maximum of a Submodular Set Function

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

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

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4178796)