A Tight Analysis of the Greedy Algorithm for Set Cover
From MaRDI portal
Publication:4373001
DOI10.1006/jagm.1997.0887zbMath0887.68040OpenAlexW2013652529MaRDI QIDQ4373001
Publication date: 18 December 1997
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jagm.1997.0887
Related Items (24)
Guarantees for the success frequency of an algorithm for finding Dodgson-election winners ⋮ Analysis of approximation algorithms for \(k\)-set cover using factor-revealing linear programs ⋮ A new approximation algorithm for \(k\)-set cover problem ⋮ Approximate \(k\)-Steiner forests via the Lagrangian relaxation technique with internal preprocessing ⋮ AN ALGORITHMIC FRAMEWORK FOR SOLVING GEOMETRIC COVERING PROBLEMS — WITH APPLICATIONS ⋮ Approximating activation edge-cover and facility location problems ⋮ Partial Resampling to Approximate Covering Integer Programs ⋮ Cost sharing and strategyproof mechanisms for set cover games ⋮ An approval-based model for single-step liquid democracy ⋮ Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover ⋮ On the approximation ability of evolutionary optimization with application to minimum set cover ⋮ On the approximability of covering points by lines and related problems ⋮ Uniform unweighted set cover: the power of non-oblivious local search ⋮ Remoteness of permutation codes ⋮ A unified approach to approximating partial covering problems ⋮ The Constant Inapproximability of the Parameterized Dominating Set Problem ⋮ Approximating \(k\)-generalized connectivity via collapsing HSTs ⋮ Finding the maximal adversary structure from any given access structure ⋮ Combinatorial optimization algorithms for radio network planning ⋮ A modified greedy algorithm for dispersively weighted 3-set cover ⋮ On approximation of the vertex cover problem in hypergraphs ⋮ Unnamed Item ⋮ A Simple Gap-Producing Reduction for the Parameterized Set Cover Problem ⋮ Tight Bounds for Single-Pass Streaming Complexity of the Set Cover Problem
This page was built for publication: A Tight Analysis of the Greedy Algorithm for Set Cover
