An approximation guarantee of the greedy descent algorithm for minimzing a supermodular set function.

DOI10.1016/S0166-218X(00)00366-8zbMath1168.90585OpenAlexW2030375943MaRDI QIDQ5954088

Victor Petrovich Il'ev

Publication date: 15 October 2002

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(00)00366-8

zbMATH Keywords

Approximation algorithmGreedy heuristicSupermodular set function

Mathematics Subject Classification ID

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

Related Items (7)

Unnamed Item ⋮ Approximate solution of the \(p\)-median minimization problem ⋮ New performance guarantees for the greedy maximization of submodular set functions ⋮ Evaluation of Combinatorial Optimisation Algorithms for c-Optimal Experimental Designs with Correlated Observations ⋮ Optimization of stochastic virus detection in contact networks ⋮ A first hitting time approach to finding effective spreaders in a network ⋮ 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
• 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

This page was built for publication: An approximation guarantee of the greedy descent algorithm for minimzing a supermodular set function.