Differential approximation algorithms for some combinatorial optimization problems

Demange, Marc; Grisoni, Pascal; Paschos, Vangelis

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

Type

Article accepté pour publication ou publié

Date

1998

Journal name

Theoretical Computer Science

Volume

209

Number

1-2

Publisher

Elsevier

Pages

107-122

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 / Keywords

Set covering; Bin-packing; Coloring; Polynomial time approximation algorithm; NP-complete problem