Covering analysis of the greedy algorithm for partial cover

DOI10.1007/978-3-642-12476-1_7MaRDI QIDQ3558262zbMATH OpenOpenAlexFDO

Authors Tapio Elomaa, Jussi Kujala

Publication date 4 May 2010

Published in Algorithms and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-12476-1_7

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Analysis of algorithms (68W40) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Recommendations

• A Tight Analysis of the Greedy Algorithm for Set Cover
• Improved performance of the greedy algorithm for partial cover
• scientific article; zbMATH DE number 1323125
• Partial covering of hypergraphs
• A Tighter Analysis of Set Cover Greedy Algorithm for Test Set

Cited in

(10)

• Refined algorithms for hitting many intervals
• Pairs Covered by a Sequence of Sets
• Improved performance of the greedy algorithm for partial cover
• A greedy algorithm to construct covering arrays using a graph representation
• A simple approximation algorithm for minimum weight partial connected set cover
• A Tighter Analysis of Set Cover Greedy Algorithm for Test Set
• Tight approximation bounds for greedy frugal coverage algorithms
• Calculating approximation guarantees for partial set cover of pairs
• Greedy algorithm for set cover in context of knowledge discovery problems
• Approximating partially bounded degree deletion on directed graphs

This page was built for publication: Covering analysis of the greedy algorithm for partial cover

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