New and improved bounds for the minimum set cover problem

DOI10.1007/978-3-642-32512-0_25zbMATH Open1372.68306OpenAlexW2106984527MaRDI QIDQ3167404FDOQ3167404

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

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

Mathematics Subject Classification ID

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

Cited In (16)

• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• The minimum-entropy set cover problem
• 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)