Master-slave strategy and polynomial approximation

A lot of minimization covering problems on graphs consist in covering verti ces or edges by subgraphs verifying a certain property. These problems can be seen as particular cases of set-covering. If the number of subgraphs is polynomial in the order n of the input-graph, then these problems can be ap proximated within logarithmic ratio by the classical greedy set-covering al gorithm. We extend the class of problems approximable by this approach to c overing problems where the number of candidate subgraphs is exponential in n, by revisiting an old technique called "master-slave" and extending it to weighted master or/and slave problems. Finally, we use the master-slave to ol to prove some positive approximation results for two network-design and a VLSI-design graph-problems.