Nonmonotone submodular maximization via a structural continuous greedy algorithm (extended abstract)

DOI10.1007/978-3-642-22006-7_29MaRDI QIDQ3012818zbMATH OpenOpenAlexFDO

Authors Moran Feldman, Joseph (Seffi) Naor, Roy Schwartz

Publication date 6 July 2011

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-22006-7_29

Mathematics Subject Classification ID

Approximation algorithms (68W25) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• Fast algorithms for maximizing monotone nonsubmodular functions
• Maximizing Non-monotone Submodular Functions
• scientific article; zbMATH DE number 7255156
• Monotone submodular maximization over a matroid via non-oblivious local search
• Maximizing non-monotone submodular set functions subject to different constraints: combined algorithms

Cites work

• An analysis of the greedy algorithm for the submodular set covering problem
• Graph cuts with interacting edge weights: examples, approximations, and algorithms
• scientific article; zbMATH DE number 3904328 (Why is no real title available?)
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Maximizing a monotone submodular function subject to a matroid constraint
• Maximizing Non-monotone Submodular Functions
• Maximizing nonmonotone submodular functions under matroid or knapsack constraints
• Submodular Approximation: Sampling-based Algorithms and Lower Bounds
• Submodular function maximization via the multilinear relaxation and contention resolution schemes
• Submodular Function Minimization under Covering Constraints
• Submodular maximization by simulated annealing
• Submodular Maximization over Multiple Matroids via Generalized Exchange Properties
• Symmetry and Approximability of Submodular Maximization Problems
• The ellipsoid method and its consequences in combinatorial optimization

Cited in

(16)

• Robust monotone submodular function maximization
• Two approximation algorithms for maximizing nonnegative weakly monotonic set functions
• An optimal monotone contention resolution scheme for bipartite matchings via a polyhedral viewpoint
• A fast algorithm for maximizing a non-monotone DR-submodular integer lattice function
• Greedy guarantees for non-submodular function maximization under independent system constraint with applications
• Bounds on double-sided myopic algorithms for unconstrained non-monotone submodular maximization
• Robust monotone submodular function maximization
• A tight linear time (1/2)-approximation for unconstrained submodular maximization
• Submodular functions: learnability, structure, and optimization
• scientific article; zbMATH DE number 7255156 (Why is no real title available?)
• Online submodular maximization with preemption
• \(k\)-submodular maximization with two kinds of constraints
• Submodular Maximization Through the Lens of Linear Programming
• Monotone submodular maximization over the bounded integer lattice with cardinality constraints
• Sequence submodular maximization meets streaming
• Approximation algorithms for multi-market competitive facility location problem with endogenous demand and diminishing marginal effect

This page was built for publication: Nonmonotone submodular maximization via a structural continuous greedy algorithm (extended abstract)

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