Differential approximation algorithms for some combinatorial optimization problems

AbstractWe 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