Année
2000
Abstract
De nombreux problèmes de minimisation de coût consistent à couvrir les sommets ou les arêtes d’un graphe par des sous-graphes vérifiant une certaine propriété. Si le nombre de sous-graphes candidats est une fonction polynomiale de la taille du graphe, l’heuristique gloutonne classique pour le Set Covering, analysée par Chvatal, permet d’approcher l’optimum à rapport logarithmique. Nous étendons ce résultat à des problèmes où le nombre de sous-graphes peut être exponentiel, en utilisant une technique dite « maître-esclave ». Les applications concernent des problèmes de télécommunication, de localisation et de conception de circuits électroniques.
ALFANDARI, L. et PASCHOS, V. (2000). Master-slave Strategy and Polynomial Approximation. Computational Optimization and Applications, pp. 231-245.