Calculating approximation guarantees for partial set cover of pairs

DOI10.1007/s11590-017-1108-yzbMath1379.90030OpenAlexW2572017251WikidataQ59612264 ScholiaQ59612264MaRDI QIDQ1676481

Peter Damaschke

Publication date: 9 November 2017

Published in: Optimization Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11590-017-1108-y

zbMATH Keywords

novelty detectiongreedy approximationextremal set familypartial set cover

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items

Optimal partial clique edge covering guided by potential energy minimization

Cites Work

• Unnamed Item
• Unnamed Item
• Partial Interval Set Cover – Trade-Offs between Scalability and Optimality
• Clique Cover and Graph Separation
• Pairs Covered by a Sequence of Sets
• A threshold of ln n for approximating set cover
• Covering Analysis of the Greedy Algorithm for Partial Cover
• A Greedy Heuristic for the Set-Covering Problem
• Improved Upper Bounds for Partial Vertex Cover
• Data reduction and exact algorithms for clique cover