New and improved bounds for the minimum set cover problem

DOI10.1007/978-3-642-32512-0_25MaRDI QIDQ3167404zbMATH OpenOpenAlexFDO

Authors Rishi Saket, Maxim Sviridenko

Publication date 2 November 2012

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-32512-0_25

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Combinatorial optimization (90C27)

Recommendations

• A threshold of ln n for approximating set cover
• Analysis of Approximation Algorithms for k-Set Cover Using Factor-Revealing Linear Programs
• Analysis of approximation algorithms for k-set cover using factor-revealing linear programs
• scientific article; zbMATH DE number 1256748
• SOFSEM 2005: Theory and Practice of Computer Science

Cited in

(19)

• A fast network-decomposition algorithm and its applications to constant-time distributed computation
• Approximating the dense set-cover problem
• Improved approximation algorithms for minimum AND-circuits problem via \(k\)-set cover
• Robust combinatorial optimization with locally budgeted uncertainty
• Restricted parameter range promise set cover problems are easy
• Improved approximation algorithms for low-density instances of the minimum entropy set cover problem
• The minimum-entropy set cover problem
• scientific article; zbMATH DE number 1670858 (Why is no real title available?)
• Parameterized exact and approximation algorithms for maximum k-set cover and related satisfiability problems
• A fast network-decomposition algorithm and its applications to constant-time distributed computation (extended abstract)
• scientific article; zbMATH DE number 1256748 (Why is no real title available?)
• An exact method for the minimum feedback arc set problem
• Tight Running Time Lower Bounds for Strong Inapproximability of Maximum k-Coverage, Unique Set Cover and Related Problems (via t-Wise Agreement Testing Theorem)
• Analysis of Approximation Algorithms for k-Set Cover Using Factor-Revealing Linear Programs
• scientific article; zbMATH DE number 5056647 (Why is no real title available?)
• Approximating minimum keys and optimal substructure screens
• An approximation algorithm for the k-prize-collecting hitting set problem
• A randomised approximation algorithm for the hitting set problem
• Analysis of approximation algorithms for k-set cover using factor-revealing linear programs

This page was built for publication: New and improved bounds for the minimum set cover problem

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