An accelerated continuous greedy algorithm for maximizing strong submodular functions

DOI10.1007/S10878-013-9685-XMaRDI QIDQ887854zbMATH OpenOpenAlexFDO

Authors Zengfu Wang, Xuezhi Wang, Quan Pan, W. Moran

Publication date 3 November 2015

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10878-013-9685-x

zbMATH Keywords

approximation algorithmmatroidcontinuous greedy algorithmmonotone submodular set function

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 5888315
• Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
• Fast algorithms for maximizing submodular functions
• Optimal approximation for the submodular welfare problem in the value oracle model
• Deterministic \(\boldsymbol{(\unicode{x00BD}+\varepsilon)}\) -Approximation for Submodular Maximization over a Matroid
• Deterministic (½ + ε)-Approximation for Submodular Maximization over a Matroid
• Maximizing non-monotone submodular set functions subject to different constraints: combined algorithms

Cites work

• scientific article; zbMATH DE number 5888315 (Why is no real title available?)
• scientific article; zbMATH DE number 3635849 (Why is no real title available?)
• A note on maximizing a submodular set function subject to a knapsack constraint
• A threshold of ln n for approximating set cover
• An analysis of approximations for maximizing submodular set functions—I
• Best Algorithms for Approximating the Maximum of a Submodular Set Function
• Combinatorial auctions with decreasing marginal utilities
• Comments on bases in dependence structures
• Inapproximability results for combinatorial auctions with submodular utility functions
• Maximizing a monotone submodular function subject to a matroid constraint
• Maximizing non-monotone submodular set functions subject to different constraints: combined algorithms
• Maximizing submodular set functions subject to multiple linear constraints
• Optimal approximation for the submodular welfare problem in the value oracle model
• Pipage rounding: a new method of constructing algorithms with proven performance guarantee
• Submodularity, Supermodularity, and Higher-Order Monotonicities of Pseudo-Boolean Functions
• The power of local search: maximum coverage over a matroid

Cited in

(2)

• Stochastic block-coordinate gradient projection algorithms for submodular maximization
• scientific article; zbMATH DE number 5670654 (Why is no real title available?)

This page was built for publication: An accelerated continuous greedy algorithm for maximizing strong submodular functions

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