Gegenbeispiel zu Max-Flow-Algorithmen mit irrationalen Gewichten?

Es ist bekannt, dass Ford-Fulkerson oder Edmonds-Karp mit der Fettrohrheuristik (zwei Algorithmen für maximalen Durchfluss) nicht anhalten müssen, wenn einige der Gewichte irrational sind. Tatsächlich können sie sogar auf den falschen Wert konvergieren ! Alle Beispiele, die ich in der Literatur finden konnte [Referenzen unten plus Referenzen darin], verwenden jedoch nur einen einzigen irrationalen Wert: den konjugierten goldenen Schnitt und andere Werte, die entweder rational oder rationale Vielfache vonϕ′ sind. Meine Hauptfrage ist:$\phi' = (\sqrt{5}-1)/2$$\phi'$

Allgemeine Frage: Was passiert mit anderen irrationalen Werten?

Zum Beispiel (aber Sie haben nicht das Gefühl, dass Sie all diese Fragen beantworten müssen, um etwas zu posten - ich würde eine interessante Antwort auf eine oder andere Fragen finden, die unter die obige allgemeine Frage fallen):

1. Kann man bei jedem solche Gegenbeispiele konstruieren (oder sogar zeigen)?$\alpha \in \mathbb{R}$

2. Schwächer: Gibt es Beispiele, die einen irrationalen Wert verwenden, der sich wesentlich von ? Das heißt, gibt es ein α, das kein rationales Vielfaches von ϕ 'ist (oder stärker nicht in Q ( ϕ ' ) ) und so, dass es Gegenbeispiele zu Ford-Fulkerson und / oder Edmonds-Karp gibt, in denen alle Gewichte liegen Q ( α ) ?$\phi'$$\alpha$$\phi'$$\mathbb{Q}(\phi')$$\mathbb{Q}(\alpha)$

3. Gibt es in der anderen Richtung ein irrationales so dass Ford-Fulkerson (bzw. Edmonds-Karp) mit dem korrekten Wert auf allen Graphen anhält, deren Gewichte alle von Q ∪ { q α : q ∈ Q } stammen ? (Oder stärker von Q ( α ) ?)$\alpha$$\mathbb{Q} \cup \{q\alpha : q \in \mathbb{Q}\}$$\mathbb{Q}(\alpha)$

In allen Fällen möchte ich so etwas wie das reale RAM-Modell annehmen, damit exakte Arithmetik und exakte Vergleiche von reellen Zahlen in konstanter Zeit durchgeführt werden.

(Es gibt andere Max-Flow-Algorithmen, von denen bekannt ist, dass sie in stark polynomialer Zeit ausgeführt werden, selbst mit beliebigen reellen Gewichten, weshalb diese Art von Frage möglicherweise nicht weiter untersucht wurde. Aber ich habe diese Algorithmen gerade in meiner Klasse für Undergrad-Algorithmen unterrichtet Ich bin immer noch neugierig darauf.)

Verweise

• Ein minimales Gegenbeispiel für Ford-Fulkerson wurde von Zwick TCS 1999 gegeben

• Ein Gegenbeispiel für Edmonds-Karp wurde von Queyranne oder Queyranne Math gegeben. Oper. Res. 1980 , obwohl ich nicht weiß, ob das minimal ist.

• Diese sind beide in Jeff Ericksons Vorlesungsunterlagen zu finden , wobei die erste in Abschnitt 23.5 und die zweite in Übung 14 von Vorlesung 23 enthalten ist.

$r$

• $n=6$$m=8$
• in denen sieben Bögen eine ganzzahlige Kapazität haben,
• $r$
• und auf dem Ford-Fulkerson möglicherweise nicht kündigen kann.

Dies wurde in der Zeitung bewiesen

Toshihiko Takahashi:
"Das einfachste und kleinste Netzwerk, in dem das Ford-Fulkerson-Verfahren mit maximalem Durchfluss
möglicherweise nicht beendet werden kann " Journal of Information Processing 24, S. 390-394, 2016.
Link: https: //www.jstage.jst.go. jp / article / ipsjjip / 24/2 / 24_390 / _article

Vielen Dank für die Frage, die ich nicht wirklich natürlich, aber dennoch ziemlich amüsant fand.

Ich habe mir den Ford-Ferkulson-Teil angesehen und ich glaube, ich habe ein Diagramm gefunden, das ein Gegenbeispiel ist und nur eine Kante mit irrationaler Kapazität α aufweist (das Diagramm kann für jedes α funktionieren).

Hier ist ein PDF, das meinen Versuch zusammenfasst: https://louis.jachiet.com/tmp/jQwbrkSMLNU_draft.pdf (Entschuldigung, es ist im Moment etwas lakonisch, aber zögern Sie nicht, Fragen zu stellen)

Natürlich können wir mit dem Ford-Felkurson den gewünschten Erweiterungspfad wählen ... Ich bin mir nicht sicher, ob dies für Edmond-Karp möglich wäre.