A randomised approximation algorithm for the hitting set problem
type: Item
instance of: scholarly article
title: A randomised approximation algorithm for the hitting set problem
zbMATH Open document ID: 1360.68903
author: Mourad El Ouali
author: Helena Fohlin
author: Anand Srivastav
published in: Theoretical Computer Science
publication date: 2014-10-06T00:00:00Z
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68W20
zbMATH DE Number: 6351404
zbMATH Keywords: approximation algorithms
zbMATH Keywords: probabilistic methods
zbMATH Keywords: randomised rounding
zbMATH Keywords: hitting set
zbMATH Keywords: vertex cover
zbMATH Keywords: greedy algorithms
MaRDI profile type: Publication
full work available at URL: j.tcs.2014.03.029
OpenAlex ID: W2037738950
cites work: Algorithmic construction of sets for k -restrictions
cites work: The probabilistic method. With an appendix on the life and work of Paul Erdős.
cites work: A linear-time approximation algorithm for the weighted vertex cover problem
cites work: Q3221758
cites work: Q3993087
cites work: A Greedy Heuristic for the Set-Covering Problem
cites work: A threshold of ln n for approximating set cover
cites work: Approximation algorithms for maximization problems arising in graph partitioning
cites work: Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
cites work: Matchings and covers in hypergraphs
cites work: Approximation algorithms for partial covering problems
cites work: Q4952635
cites work: Approximation Algorithms for the Set Covering and Vertex Cover Problems
cites work: A fast approximation algorithm for the multicovering problem
cites work: Improved approximation algorithms for maximum graph partitioning problems
cites work: Approximation algorithms for combinatorial problems
cites work: Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
cites work: Approximate Set Covering in Uniform Hypergraphs
cites work: On the ratio of optimal integral and fractional covers
cites work: On the hardness of approximating minimization problems
cites work: Q4226453
cites work: Randomized approximation of bounded multicovering problems
cites work: On approximation of the vertex cover problem in hypergraphs
cites work: Q4527015
cites work: New and Improved Bounds for the Minimum Set Cover Problem
DOI: 10.1016/J.TCS.2014.03.029
description: scientific article; zbMATH DE number 6351404