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

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

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

(16)

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

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)