Nonmonotone Submodular Maximization via a Structural Continuous Greedy Algorithm

DOI10.1007/978-3-642-22006-7_29zbMath1332.68285OpenAlexW1542515633MaRDI QIDQ3012818

Moran Feldman, Roy Schwartz, Joseph (Seffi) Naor

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 methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items (14)

A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization ⋮ Maximizing Symmetric Submodular Functions ⋮ Robust Monotone Submodular Function Maximization ⋮ Submodular Functions: Learnability, Structure, and Optimization ⋮ Bounds on Double-Sided Myopic Algorithms for Unconstrained Non-monotoneSubmodular Maximization ⋮ Submodular Maximization Through the Lens of Linear Programming ⋮ A fast algorithm for maximizing a non-monotone DR-submodular integer lattice function ⋮ Monotone submodular maximization over the bounded integer lattice with cardinality constraints ⋮ Sequence submodular maximization meets streaming ⋮ Robust monotone submodular function maximization ⋮ Online Submodular Maximization with Preemption ⋮ k-Submodular maximization with two kinds of constraints ⋮ Two approximation algorithms for maximizing nonnegative weakly monotonic set functions ⋮ An optimal monotone contention resolution scheme for bipartite matchings via a polyhedral viewpoint

Cites Work

• Unnamed Item
• Unnamed Item
• Graph cuts with interacting edge weights: examples, approximations, and algorithms
• The ellipsoid method and its consequences in combinatorial optimization
• An analysis of the greedy algorithm for the submodular set covering problem
• Maximizing Nonmonotone Submodular Functions under Matroid or Knapsack Constraints
• Maximizing Non-monotone Submodular Functions
• Submodular Approximation: Sampling-based Algorithms and Lower Bounds
• Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Submodular Function Minimization under Covering Constraints
• Symmetry and Approximability of Submodular Maximization Problems
• Submodular function maximization via the multilinear relaxation and contention resolution schemes
• Submodular Maximization over Multiple Matroids via Generalized Exchange Properties

This page was built for publication: Nonmonotone Submodular Maximization via a Structural Continuous Greedy Algorithm