SUR LES α-FLOTS

摘要

La présente note contient quelques remarques sur les résultats de Minoux exposés dans. Nous signalons que les méthodes proposées pour résoudre le problème des α-flots maximaux et des flots à taux de sécurité maximal peuvent dégénérer et ne convergent pas toujours vers les solutions optimales. Nous montrons que les solutions de ces problèmes peuvent être obtenues très simplement par des méthodes classiques. Nous proposons un algorithme glouton fortement polynomial, basé sur la méthode de Newton couplée avec l'algorithme de flot maximum. L'efficacité des méthodes dichotomiques classiques pour ces problèmes est signalée.%We take up Minoux ideas which are explained in [2]. We point out that the algorithms he has proposed to solve the problem of maximum α-flow and flow with a maximum rate of safety fail. We propose a simple and efficient, greedy, strongly polynomial algorithm based on Newton's method and max-flow algorithm.