Approximating the dense set-cover problem

DOI10.1016/J.JCSS.2004.03.006MaRDI QIDQ1765297zbMATH OpenOpenAlexFDO

Authors Zehavit Kehat, Reuven Bar-Yehuda

Publication date 23 February 2005

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jcss.2004.03.006

zbMATH Keywords

Approximation algorithmSet-coverVertex-cover

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• scientific article; zbMATH DE number 1163714
• Approximating vertex cover on dense graphs
• scientific article; zbMATH DE number 1594511
• New and improved bounds for the minimum set cover problem
• Approximating vertex cover in dense hypergraphs

Cites work

• scientific article; zbMATH DE number 1594511 (Why is no real title available?)
• scientific article; zbMATH DE number 3889282 (Why is no real title available?)
• scientific article; zbMATH DE number 1163714 (Why is no real title available?)
• scientific article; zbMATH DE number 1445320 (Why is no real title available?)
• A linear-time approximation algorithm for the weighted vertex cover problem
• An approximation of the minimum vertex cover in a graph
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• Approximation algorithms for combinatorial problems
• Ramsey numbers and an approximation algorithm for the vertex cover problem
• Vertex packings: Structural properties and algorithms

Cited in

(21)

• Approximating \(k\)-set cover and complementary graph coloring
• Connected Vertex Covers in Dense Graphs
• A note on the set union knapsack problem
• Approximating the Unweighted ${k}$-Set Cover Problem: Greedy Meets Local Search
• Improved approximation algorithms for low-density instances of the minimum entropy set cover problem
• scientific article; zbMATH DE number 2081015 (Why is no real title available?)
• scientific article; zbMATH DE number 1594511 (Why is no real title available?)
• Connected vertex covers in dense graphs
• Approximation preserving reductions for set covering, vertex covering and independent set hierarchies under differential approximationa
• A threshold of ln n for approximating set cover
• Approximating minimum keys and optimal substructure screens
• Approximating subdense instances of covering problems
• Approximating edge dominating set in dense graphs
• Nearly tight approximation bounds for vertex cover on dense \(k\)-uniform \( k\)-partite hypergraphs
• Approximating edge dominating set in dense graphs
• CLUSTAG & WCLUSTAG: Hierarchical Clustering Algorithms for Efficient Tag-SNP Selection
• Benchmark data set with service programs to approximately solve the set covering problem
• Improved (In-)Approximability Bounds for d-Scattered Set
• Optimization through dense sets
• Exact algorithms for problems related to the densest \(k\)-set problem
• Approximating vertex cover in dense hypergraphs

This page was built for publication: Approximating the dense set-cover problem

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