Approximation preserving reductions for set covering, vertex covering and independent set hierarchies under differential approximation
Ekim, Tinaz; Paschos, Vangelis (2004), Approximation preserving reductions for set covering, vertex covering and independent set hierarchies under differential approximation, International Journal of Computer Mathematics, 81, 5, p. 569-582. http://dx.doi.org/10.1080/00207160410001688592
Type
Article accepté pour publication ou publiéDate
2004Journal name
International Journal of Computer MathematicsVolume
81Number
5Publisher
Taylor & Francis
Pages
569-582
Publication identifier
Metadata
Show full item recordAbstract (EN)
The notion of approximability preserving reductions between different problems deserves special attention in approximability theory. These kinds of reductions allow us polynomial time conversion of some already known 'good' approximation algorithms for some NP-hard problems into ones for some other NP-hard problems. In this context, we consider reductions for set covering and vertex covering hierarchies. Our results are then extended to hitting set and independent set hierarchies. Here, we adopt the differential approximation ratio that has the natural property to be stable under affine transformations of the objective function of a problem.Subjects / Keywords
Vertex covering; Set covering; Hierarchy; Differential approximation ratio; Approximability preserving reductionsRelated items
Showing items related by title and author.
-
Paschos, Vangelis (1994) Article accepté pour publication ou publié
-
Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis (2011) Article accepté pour publication ou publié
-
Bourgeois, N.; Catellier, Rémi; Denat, T.; Paschos, Vangelis (2015) Document de travail / Working paper
-
Paschos, Vangelis; Demange, Marc (1997) Article accepté pour publication ou publié
-
Paschos, Vangelis; Pekergin, Ferhan; Zissimopoulos, Vassilis (1992) Communication / Conférence