Differential approximation algorithms for some combinatorial optimization problems
Demange, Marc; Grisoni, Pascal; Paschos, Vangelis (1998), Differential approximation algorithms for some combinatorial optimization problems, Theoretical Computer Science, 209, 1-2, p. 107-122. http://dx.doi.org/10.1016/S0304-3975(97)00099-6
TypeArticle accepté pour publication ou publié
Journal nameTheoretical Computer Science
MetadataShow full item record
Abstract (EN)We use a new approximation measure, the differential approximation ratio, to derive polynomial-time approximation algorithms for minimum set covering (for both weighted and unweighted cases), minimum graph coloring and bin-packing. We also propose differential-approximation-ratio preserving reductions linking minimum coloring, minimum vertex covering by cliques, minimum edge covering by cliques and minimum edge covering of a bipartite graph by complete bipartite graphs.
Subjects / KeywordsSet covering; Bin-packing; Coloring; Polynomial time approximation algorithm; NP-complete problem
Showing items related by title and author.
The approximability behavior of some combinatorial problems with respect to the approximability of a class of maximum independent set problems Demange, Marc; Paschos, Vangelis (1997) Article accepté pour publication ou publié