Hereditary systems and greedy-type algorithms.
From MaRDI portal
Publication:1414589
DOI10.1016/S0166-218X(03)00396-2zbMath1052.90063MaRDI QIDQ1414589
Publication date: 4 December 2003
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
maximum independent set problemRado-Edmonds theoremComatroidGreedy-type approximation algorithmHereditary systemmaximum dependent set problemPerformance guaranteeSteepest descent algorithm
Combinatorial optimization (90C27) Combinatorial aspects of matroids and geometric lattices (05B35) Coloring of graphs and hypergraphs (05C15)
Related Items
Performance guarantees of forward and reverse greedy algorithms for minimizing nonsupermodular nonsubmodular functions on a matroid ⋮ A comment on performance guarantees of a greedy algorithm for minimizing a supermodular set function on comatroid ⋮ Minimum partition of an independence system into independent sets
Cites Work