A comment on performance guarantees of a greedy algorithm for minimizing a supermodular set function on comatroid

DOI10.1016/J.EJOR.2020.07.047MaRDI QIDQ2029356zbMATH OpenOpenAlexFDO

Authors Orcun Karaca, Baiwei Guo, Maryam Kamgarpour

Publication date 3 June 2021

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

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

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

zbMATH Keywords

combinatorial optimizationgreedy algorithmmatroid theory

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Coloring of graphs and hypergraphs (05C15) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Abstract: We provide a counterexample to the performance guarantee obtained in the paper "Performance guarantees of a greedy algorithm for minimizing a supermodular set function on comatroid", which was published in Volume 171 of the European Journal of Operational Research. We comment on where this error originates from in the proof of the main theorem.

Recommendations

• Performance guarantees of a greedy algorithm for minimizing a supermodular set function on comatroid
• New performance guarantees for the greedy maximization of submodular set functions
• scientific article; zbMATH DE number 2032337
• Correction to: ``Guess free maximization of submodular and linear sums
• Corrigendum to our paper The ellipsoid method and its consequences in combinatorial optimization

Cites work

• Hereditary systems and greedy-type algorithms.
• Performance guarantees of a greedy algorithm for minimizing a supermodular set function on comatroid

Cited in

(2)

• Performance guarantees of forward and reverse greedy algorithms for minimizing nonsupermodular nonsubmodular functions on a matroid
• Performance guarantees of a greedy algorithm for minimizing a supermodular set function on comatroid

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

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