New performance guarantees for the greedy maximization of submodular set functions

DOI10.1007/s11590-016-1039-zzbMath1368.90124arXiv1506.00423OpenAlexW2239902130MaRDI QIDQ523157

Jussi Laitila, Atte Moilanen

Publication date: 20 April 2017

Published in: Optimization Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1506.00423

zbMATH Keywords

convex optimizationapproximationgreedy algorithmcardinalitymaximizationsteepest ascent

Mathematics Subject Classification ID

Convex programming (90C25) Approximation methods and heuristics in mathematical programming (90C59)

Related Items (7)

Exact hypervolume subset selection through incremental computations ⋮ Two-stage non-submodular maximization ⋮ Two-stage BP maximization under \(p\)-matroid constraint ⋮ Two-stage non-submodular maximization ⋮ Two-stage BP maximization under \(p\)-matroid constraint ⋮ Two-stage submodular maximization under curvature ⋮ Improved algorithms for non-submodular function maximization problem

Cites Work

• Budgeted nature reserve selection with diversity feature loss and arbitrary split systems
• Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
• Performance guarantees of a greedy algorithm for minimizing a supermodular set function on comatroid
• A note on maximizing a submodular set function subject to a knapsack constraint
• Maximizing Non-monotone Submodular Functions
• Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
• Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms
• An analysis of approximations for maximizing submodular set functions—I
• Best Algorithms for Approximating the Maximum of a Submodular Set Function
• Approximations for Monotone and Nonmonotone Submodular Maximization with Knapsack Constraints
• Matroids and the greedy algorithm
• An approximation guarantee of the greedy descent algorithm for minimzing a supermodular set function.
• Approximation for maximizing monotone non-decreasing set functions with a greedy method
• Unnamed Item
• Unnamed Item

This page was built for publication: New performance guarantees for the greedy maximization of submodular set functions