Couverture de bord pondérée minimale - l'algorithme glouton est-il sous-optimal?

Nov 27 2020

Le message ici: La résolution de la couverture minimale des bords à l'aide de l'algorithme de correspondance maximale fournit un moyen d'obtenir la couverture minimale des bords à partir d'une correspondance maximale en ajoutant avidement des bords au-dessus de la correspondance maximale jusqu'à ce que tous les sommets soient couverts. Maintenant, en pensant au problème de couverture de bord min pondéré, il semblerait que cette approche puisse être étendue. Tout d'abord, trouvez la correspondance pondérée minimale avec les arêtes maximales , puis ajoutez les arêtes du poids le plus petit avec gourmandise, d'abord celles du poids le plus petit.

Cependant, en lisant la section 19.3 du livre «Optimisation combinatoire: polyèdres et efficacité» de Schrijver, un algorithme plus compliqué est présenté. Cela donne l'impression que mon approche ci-dessus est sous-optimale. Est-il possible de trouver un contre-exemple, de préférence sur un graphe bi-partite où mon algorithme gourmand échouerait à fournir une solution optimale? Je n'ai pas pu en trouver un avec des graphiques de jouets.

Réponses

1 j_random_hacker Nov 28 2020 at 04:01

Voici un contre-exemple à votre algorithme proposé:

La solution optimale se compose de 3 arêtes et coûte 3 + 1 + 1 = 5, mais la correspondance de cardinalité maximale de coût min, qui se compose de 2 arêtes et coûte 3 + 3 = 6, sera choisie par la première étape de votre algorithme et immédiatement retourné, car c'est déjà une solution. (La seule autre correspondance de cardinalité maximale coûte 1 + 6 = 7.)