最小加重エッジカバー-欲張りアルゴリズムは最適ではありませんか？
Nov 27 2020
ここでの投稿：最大マッチングアルゴリズムを使用して最小エッジカバーを解くと、すべての頂点がカバーされるまで最大マッチングの上にエッジを貪欲に追加することで、最大マッチングから最小エッジカバーを取得する方法が提供されます。ここで、最小加重エッジカバーの問題について考えると、このアプローチは拡張できるように思われます。まず、最大のエッジを持つ最小の重み付きマッチングを見つけ、次に最小の重みのエッジを貪欲に追加し、最初に最小の重みのエッジを追加します。
ただし、Schrijverによる本「組み合わせの最適化：多面体と効率」のセクション19.3を読むと、より複雑なアルゴリズムが提示されます。これにより、上記の私のアプローチは最適ではないように見えます。反例を見つけることは可能ですか？できれば、欲張りアルゴリズムが最適なソリューションを提供できない2部グラフで見つけることができますか？おもちゃのグラフがいくつかあるものを見つけることができませんでした。
回答
1 j_random_hacker Nov 28 2020 at 04:01
提案されたアルゴリズムの反例は次のとおりです。
最適なソリューションは3つのエッジで構成され、コストは3 + 1 + 1 = 5ですが、2つのエッジで構成され、コストが3 + 3 = 6である最小コストの最大カーディナリティーマッチングは、アルゴリズムの最初のステップで選択されます。それはすでに解決策であるため、すぐに返されました。（他の最大カーディナリティーマッチングのコストは1 + 6 = 7のみです。）