Master-slave strategies and polynomial approximation
Alfandari, Laurent; Paschos, Vangelis (2000), Master-slave strategies and polynomial approximation, Computational Optimization and Applications, 16, p. 231-245
Type
Article accepté pour publication ou publiéExternal document link
http://www.lamsade.dauphine.fr/FILES/publi154.pdfDate
2000Journal name
Computational Optimization and ApplicationsVolume
16Publisher
Springer
Pages
231-245
Metadata
Show full item recordAbstract (EN)
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 ldquomaster-slaverdquo 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.Subjects / Keywords
set-covering; network design; approximation; combinatorial optimizationRelated items
Showing items related by title and author.
-
Alfandari, Laurent; Paschos, Vangelis (1998) Communication / Conférence
-
Paschos, Vangelis (2013) Communication / Conférence
-
Demange, Marc; Paschos, Vangelis (1996) Article accepté pour publication ou publié
-
Paschos, Vangelis (2003) Article accepté pour publication ou publié
-
Demange, Marc; Monnot, Jérôme; Paschos, Vangelis (1999) Article accepté pour publication ou publié