非合理的な重みを持つmax-flowアルゴリズムの例

Ford-FulkersonまたはEdmonds-Karpが太いパイプヒューリスティック(max-flowの2つのアルゴリズム)を使用すると、重みの一部が非合理的である場合に停止する必要はないことが知られています。実際には、間違った値に収束することもあります。しかし、私が文献で見つけることができるすべての例は、共役黄金比$
phi ‘=( sqrt {5} -1)/ 2 $、およびその他合理的な値、または$ phi
‘$の有理数倍の値です。私の主な質問は:

一般的な質問:他の不合理な値はどうなりますか?

たとえば、これらのすべてに答える必要があるとは思わない(私は、いずれかの回答や上記の一般的な質問に該当する他の質問に興味深いと思う)。

  1. Given any $alpha in mathbb{R}$, can one construct (or even
    show existence of) such counterexamples?

  2. More weakly: are there examples known that use an irrational
    value essentially different from $phi’$? That is, is
    there some $alpha$ which is not a rational multiple of $phi’$ (or
    more strongly not in $mathbb{Q}(phi’)$) and such that there are
    counterexamples to Ford-Fulkerson and/or Edmonds-Karp where all the
    weights lie in $mathbb{Q}(alpha)$?

  3. In the other direction, does there exist an irrational $alpha$
    such that Ford-Fulkerson (resp., Edmonds-Karp) halts with the
    correct value on all graphs whose weights are all from
    $mathbb{Q} cup {qalpha : q in mathbb{Q}}$? (Or more
    strongly, from $mathbb{Q}(alpha)$?)

すべての場合において、実際のRAMモデルのようなものを仮定したいので、実数の正確な比較と正確な比較は一定の時間内に行われます。

(多項式時間で実行することが知られている他のmax-flowアルゴリズムもありますが、これはおそらくこのタイプの質問がさらに探究されなかったのかもしれませんが、私の学部のアルゴリズムクラス、私はまだこれについて興味がある。)

参照

ベストアンサー

答えは、すべての不合理な数$ r $に対して、ネットワークが存在することです

  • $ n = 6 $ verticesと$ m = 8 $ arcで、
  • 7つのアークが整数の容量を持つ
  • 1つの円弧に容量$ r $がある
  • Ford-Fulkersonが終了しない可能性があります。

これは論文で証明されています

高橋俊彦:
  「Ford-Fulkersonの最大フロー手順が終了しない可能性のある最も単純で小さなネットワーク」
  Journal of Information Processing 24、pp
390-394、2016.
  リンク: https://www.jstage.jst.go .jp /記事/
ipsjjip/24/2/24_390/_article

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です