A survey on double greedy algorithms for maximizing non-monotone submodular functions

DOI10.1007/978-3-030-41672-0_10MaRDI QIDQ3297828zbMATH OpenOpenAlexFDO

Authors Suning Gong, Qizhi Fang, Du Ding-Zhu, Qingqin Nong

Publication date 20 July 2020

Published in Complexity and Approximation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-030-41672-0_10

zbMATH Keywords

submodular functiondouble greedy algorithmnon-monotone function

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• A fast double greedy algorithm for non-monotone DR-submodular function maximization
• Non-monotone submodular maximization under matroid and knapsack constraints
• A binary search double greedy algorithm for non-monotone DR-submodular maximization
• Submodular maximization with cardinality constraints
• Fast algorithms for maximizing monotone nonsubmodular functions

Cites work

• A Unified Continuous Greedy Algorithm for Submodular Maximization
• A tight linear time (1/2)-approximation for unconstrained submodular maximization
• About strongly polynomial time algorithms for quadratic optimization over submodular constraints
• An efficient algorithm for image segmentation, Markov random fields and related problems
• Deterministic Algorithms for Submodular Maximization Problems
• Learning submodular functions
• Maximizing Non-monotone Submodular Functions
• Maximizing a class of submodular utility functions
• Online submodular welfare maximization: greedy is optimal
• Submodular function maximization on the bounded integer lattice
• Submodular functions: from discrete to continuous domains
• Submodular maximization by simulated annealing
• Submodular maximization with cardinality constraints
• Unconstrained submodular maximization with constant adaptive complexity

Cited in

(3)

• A binary search double greedy algorithm for non-monotone DR-submodular maximization
• Profit maximization in social networks and non-monotone DR-submodular maximization
• A fast double greedy algorithm for non-monotone DR-submodular function maximization

This page was built for publication: A survey on double greedy algorithms for maximizing non-monotone submodular functions

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