Performance guarantees of a greedy algorithm for minimizing a supermodular set function on comatroid

DOI10.1016/J.EJOR.2004.09.026zbMath1162.90545OpenAlexW1981719462MaRDI QIDQ817555

Nick Linker, Victor Petrovich Il'ev

Publication date: 16 March 2006

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2004.09.026

zbMATH Keywords

heuristicscombinatorial optimizationsupermodular set functionperformance guaranteecomatroid

Mathematics Subject Classification ID

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

Related Items (4)

Performance guarantees of forward and reverse greedy algorithms for minimizing nonsupermodular nonsubmodular functions on a matroid ⋮ Approximate solution of the \(p\)-median minimization problem ⋮ New performance guarantees for the greedy maximization of submodular set functions ⋮ A comment on performance guarantees of a greedy algorithm for minimizing a supermodular set function on comatroid

Cites Work

• Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• 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
• An approximation guarantee of the greedy descent algorithm for minimzing a supermodular set function.

This page was built for publication: Performance guarantees of a greedy algorithm for minimizing a supermodular set function on comatroid