Retour aux résultats
Articles (2000), Computational Optimization and Applications, pp. 231-245

Master-slave Strategy and Polynomial Approximation

ALFANDARI Laurent , PASCHOS V.

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. and PASCHOS, V. (2000). Master-slave Strategy and Polynomial Approximation. Computational Optimization and Applications, pp. 231-245.