DIFFERENTIAL APPROXIMATION ALGORITHMS FOR SOME COMBINATORIAL OPTIMIZATION PROBLEMS

Authors
DEMANGE M GRISONI P PASCHOS VT
Citation
M. Demange et al., DIFFERENTIAL APPROXIMATION ALGORITHMS FOR SOME COMBINATORIAL OPTIMIZATION PROBLEMS, Theoretical computer science, 209(1-2), 1998, pp. 107-122
Citations number
20
Categorie Soggetti
Computer Science Theory & Methods","Computer Science Theory & Methods
Journal title
Theoretical computer science → ACNP
ISSN journal
03043975
Volume
209
Issue
1-2
Year of publication
1998
Pages
107 - 122
Database
ISI
SICI code
0304-3975(1998)209:1-2<107:DAAFSC>2.0.ZU;2-2
Abstract
We use a new approximation measure, the differential approximation rat io, to derive polynomial-time approximation algorithms for minimum set covering (for both weighted and unweighted cases), minimum graph colo ring and bin-packing. We also propose differential-approximation-ratio preserving reductions linking minimum coloring, minimum vertex coveri ng by cliques, minimum edge covering by cliques and minimum edge cover ing of a bipartite graph by complete bipartite graphs. (C) 1998-Elsevi er Science B.V. All rights reserved.