A note on submodular set cover on matroids

DOI10.1016/J.DISC.2008.05.019zbMath1207.05028OpenAlexW2071109974MaRDI QIDQ1045066

Luisa Gargano, Mikael Hammar

Publication date: 15 December 2009

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

Full work available at URL: https://doi.org/10.1016/j.disc.2008.05.019

zbMATH Keywords

matroidindependent setsset cover

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The ellipsoid method and its consequences in combinatorial optimization
• On the ratio of optimal integral and fractional covers
• An analysis of the greedy algorithm for the submodular set covering problem
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• A threshold of ln n for approximating set cover
• Theory of submodular programs: A fenchel-type min-max theorem and subgradients of submodular functions
• A weighted matroid intersection algorithm
• Maximising Real-Valued Submodular Functions: Primal and Dual Heuristics for Location Problems

This page was built for publication: A note on submodular set cover on matroids