Hereditary systems and greedy-type algorithms.

DOI10.1016/S0166-218X(03)00396-2zbMath1052.90063MaRDI QIDQ1414589

Victor Petrovich Il'ev

Publication date: 4 December 2003

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

zbMATH Keywords

maximum independent set problemRado-Edmonds theoremComatroidGreedy-type approximation algorithmHereditary systemmaximum dependent set problemPerformance guaranteeSteepest descent algorithm

Mathematics Subject Classification ID

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

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Note on Independence Functions
• A Greedy Heuristic for the Set-Covering Problem
• An Analysis of the Greedy Heuristic for Independence Systems
• Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching
• Matroids and the greedy algorithm