Efficient approximation of Min Set Cover by moderately exponential algorithms
type: Item
instance of: scholarly article
title: Efficient approximation of Min Set Cover by moderately exponential algorithms
zbMATH Open document ID: 1166.68043
author: Bruno Escoffier
author: Nicolas Bourgeois
author: Vangelis Th. Paschos
published in: Theoretical Computer Science
publication date: 2009-05-28T00:00:00Z
full work available at URL: https://basepub.dauphine.fr/handle/123456789/2098
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 5559000
zbMATH Keywords: exponential algorithms
zbMATH Keywords: approximation algorithms
zbMATH Keywords: Min Set Cover
MaRDI profile type: Publication
OpenAlex ID: W2009411756
cites work: Proof verification and the hardness of approximation problems
cites work: Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness
cites work: On the differential approximation of MIN SET COVER
cites work: 3-coloring in time
cites work: Q3941433
cites work: Set Partitioning via Inclusion-Exclusion
cites work: Fixed-Parameter Approximation: Conceptual Framework and Approximability Results
cites work: On Parameterized Approximability
cites work: A Greedy Heuristic for the Set-Covering Problem
cites work: Differential approximation algorithms for some combinatorial optimization problems
cites work: On an approximation measure founded on the links between optimization and polynomial approximation theory
cites work: Parameterized Approximation Problems
cites work: A threshold of ln n for approximating set cover
cites work: Q3396567
cites work: A modified greedy heuristic for the set covering problem with improved worst case bound
cites work: A note on the complexity of minimum dominating set
cites work: \(z\)-approximations
cites work: Approximation Algorithms for the Set Covering and Vertex Cover Problems
cites work: Approximation algorithms for combinatorial problems
cites work: Q4142699
cites work: Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
cites work: On the ratio of optimal integral and fractional covers
cites work: Non deterministic polynomial optimization problems and their approximations
cites work: STACS 2005
cites work: Q4910758
cites work: Confronting hardness using a hybrid approach
cites work: Q4414647
DOI: 10.1016/J.TCS.2009.02.007
Recommended article: Q4411280
Recommended article: Q4843442
Recommended article: A Better-Than-Greedy Approximation Algorithm for the Minimum Set Cover Problem
Recommended article: Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
Recommended article: Approximating min sum set cover
Recommended article: Exponential-time approximation of weighted set cover
Recommended article: Tight bounds on subexponential time approximation of set cover and related problems
Recommended article: On the differential approximation of MIN SET COVER
Recommended article: Algorithms – ESA 2005
Recommended article: Q5417729
description: scientific article; zbMATH DE number 5559000