caa a22 4500 475750373 CHVBK 20180406123521.0 cr unu---uuuuu 170329e20000901xx s 000 0 eng 10.1023/A:1008764212265 doi (NATIONALLICENCE)springer-10.1023/A:1008764212265 Master-Slave Strategy and Polynomial Approximation [Elektronische Daten] [Laurent Alfandari, Vangelis Paschos] A lot of minimization covering problems on graphs consist in covering vertices 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 approximated within logarithmic ratio by the classical greedy set-covering algorithm. We extend the class of problems approximable by this approach to covering 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 tool to prove some positive approximation results for two network-design and a VLSI-design graph-problems. Kluwer Academic Publishers, 2000 combinatorial optimization nationallicence approximation nationallicence network design nationallicence set-covering nationallicence Alfandari Laurent Place du Maréchal De Lattre de Tassigny, LAMSADE, Université Paris-Dauphine, 75775, Paris Cedex 16, France aut Paschos Vangelis Place du Maréchal De Lattre de Tassigny, LAMSADE, Université Paris-Dauphine, 75775, Paris Cedex 16, France aut Computational Optimization and Applications Kluwer Academic Publishers 16/3(2000-09-01), 231-245 0926-6003 16:3<231 2000 16 10589 https://doi.org/10.1023/A:1008764212265 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1023/A:1008764212265 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Alfandari Laurent Place du Maréchal De Lattre de Tassigny, LAMSADE, Université Paris-Dauphine, 75775, Paris Cedex 16, France aut NATIONALLICENCE 700 1- Paschos Vangelis Place du Maréchal De Lattre de Tassigny, LAMSADE, Université Paris-Dauphine, 75775, Paris Cedex 16, France aut NATIONALLICENCE 773 0- Computational Optimization and Applications Kluwer Academic Publishers 16/3(2000-09-01), 231-245 0926-6003 16:3<231 2000 16 10589 Metadata rights reserved Springer special CC-BY-NC licence nationallicence SWISSBIB 231331185 BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer