Nos tutelles

CNRS Dauphine PSL *


Accueil > Projets > Autres > Documents

Approximation algorithms for some combinatorial optimization problems. (V.Th. PASCHOS, P. GRISONI, M. DEMANGE)

publié le

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 and minimum edge covering of a bipartite graph by complete bipartite graphs.

Keywords : NP- complete problem, polynomial time approximation algorithm, set covering, coloring, bin-packing