On the differential approximation of MIN SET COVER
type: Item
instance of: scholarly article
title: On the differential approximation of MIN SET COVER
zbMATH Open document ID: 1070.68153
author: Cristina Bazgan
author: Vangelis Th. Paschos
author: Fabrice Serriére
author: Jérôme Monnot
published in: Theoretical Computer Science
publication date: 2005-04-06T00:00:00Z
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 90C59
zbMATH DE Number: 2153199
zbMATH Keywords: Approximation algorithms
zbMATH Keywords: Complexity
zbMATH Keywords: Set cover
zbMATH Keywords: Combinatorial problem
zbMATH Keywords: Greedy algorithm
MaRDI profile type: Publication
full work available at URL: j.tcs.2004.12.022
OpenAlex ID: W2092740206
cites work: Q4725744
cites work: Structure preserving reductions among convex optimization problems
cites work: Toward a unified approach for the classification of NP-complete optimization problems
cites work: Q4258216
cites work: Q3142706
cites work: On an approximation measure founded on the links between optimization and polynomial approximation theory
cites work: Improved approximations for maximum independent set via approximation chains
cites work: Differential approximation algorithms for some combinatorial optimization problems
cites work: Approximations of Weighted Independent Set and Hereditary Subset Problems
cites work: \(z\)-approximations
cites work: The maximum saving partition problem
cites work: Approximation algorithms for combinatorial problems
cites work: On the ratio of optimal integral and fractional covers
cites work: Q4228498
cites work: Measuring the Quality of Approximate Solutions to Zero-One Programming Problems
DOI: 10.1016/J.TCS.2004.12.022
description: scientific article; zbMATH DE number 2153199