$O(\log n)$-Approximationsalgorithmen für Bipartiteness Ratio

Grundinformationen

• Paper-ID: 2507.12847
• Titel: $O(\log n)$-Approximationsalgorithmen für Bipartiteness Ratio
• Autoren: Tasuku Soma (The Institute of Statistical Mathematics & RIKEN AIP), Mingquan Ye (National Institute of Informatics & University of California, Santa Cruz), Yuichi Yoshida (National Institute of Informatics)
• Klassifizierung: cs.DS (Datenstrukturen und Algorithmen)
• Veröffentlichungsdatum: 5. November 2025 (arXiv v2)
• Paper-Link: https://arxiv.org/abs/2507.12847

Zusammenfassung

Dieses Paper präsentiert den ersten $O(\log n)$-Approximationsalgorithmus für das Bipartiteness-Ratio-Problem ungerichteter Graphen, wobei $n$ die Anzahl der Knoten ist. Die Methode erweitert das Cut-Matching-Game-Framework vom Sparsest-Cut-Problem auf das Bipartiteness-Ratio-Problem und erfordert nur $\text{polylog } n$ Berechnungen von Single-Commodity-Ungerichteten-Maximalflüssen. In Kombination mit den schnellsten bekannten Ungerichteten-Maximalfluss-Algorithmen wird eine quasi-lineare Zeitkomplexität erreicht. Die Forschung führt das Konzept der guten Verbundenheit (well-linkedness) für halbsymmetrische Graphen ein und beweist eine neue Charakterisierung des Bipartiteness Ratio bezüglich guter Verbundenheit in Hilfshalbsymmetrischen Graphen. Als Anwendung wird ein $\tilde{O}(mn)$-Zeit-Algorithmus für Minimum Uncut präsentiert. Darüber hinaus wird das gerichtete Bipartiteness Ratio definiert und ein $O(\log n)$-Approximationsalgorithmus durch gerichtete Leighton-Rao-ähnliche Einbettung bereitgestellt.

Forschungshintergrund und Motivation

Problemdefinition

Das Bipartiteness-Ratio-Problem wurde von Trevisan Tre12 eingeführt. Für einen ungerichteten Graphen $G=(V,E,w)$ wird definiert: $\beta(G) := \min_{x\in\{0,\pm1\}^V\setminus\{0\}} \frac{\sum_{e=(i,j)\in E} w(e)\cdot|x_i+x_j|}{\sum_{i\in V} \deg(i)\cdot|x_i|}$

Dieses Verhältnis charakterisiert die Abweichung eines Graphen von einem bipartiten Graphen: $\beta(G)=0$ genau dann, wenn $G$ bipartit ist.

Forschungsbedeutung

1. Theoretische Bedeutung: Das Bipartiteness Ratio ist ein Kernkonzept der dualen Cheeger-Ungleichung und steht in enger Beziehung zum größten Eigenwert $\lambda_n$ der normalisierten Laplace-Matrix: $\frac{2-\lambda_n}{2} \leq \beta(G) \leq \sqrt{2(2-\lambda_n)}$
2. Anwendungswert:
   • Spektrale Algorithmenentwicklung: Trevisan nutzte diese Ungleichung zur Entwicklung eines rein spektralen Algorithmus für Max-Cut
   • Netzwerkanalyse: Anwendungen in vorzeichenbehafteter Graphen-Clusterung, Gemeinschaftserkennung und verwandten Bereichen XOG20; AL20; NP22
   • Kombinatorische Optimierung: Enge Beziehung zu klassischen Problemen wie Max-Cut und Minimum Uncut

Einschränkungen bestehender Methoden

1. Mangel an Approximationsalgorithmen: Obwohl Cheeger-Ungleichungen und Sparsest Cut etablierte Approximationsalgorithmen haben (wie $O(\sqrt{\log n})$-Approximation), gab es für das Bipartiteness Ratio bisher keinen polynomiellen Approximationsalgorithmus
2. Unzulänglichkeit spektraler Methoden: Bestehende spektrale Methoden (basierend auf Eigenvektoren) können nur theoretische Grenzen liefern, nicht direkt Optimierungsprobleme lösen
3. Unterschiede zu Sparsest Cut: Obwohl das Bipartiteness Ratio formal ähnlich wie Sparsest Cut aussieht, machen seine Nebenbedingungen (Drei-Partition-Struktur) die direkte Anwendung bestehender Techniken schwierig

Forschungsmotivation

Schließung der Lücke bei Approximationsalgorithmen für das Bipartiteness Ratio und Bereitstellung neuer algorithmischer Werkzeuge für Graphenspektraltheorie und kombinatorische Optimierung.

Kernbeiträge

1. Erster Approximationsalgorithmus: Präsentation des ersten $O(\log n)$-Approximationsalgorithmus für das $b$-Bipartiteness Ratio mit Zeitkomplexität $\tilde{O}(\min\{b(V),n^2\}+m)$
2. Theoretische Innovationen:
   • Einführung des Konzepts der guten Verbundenheit (well-linkedness) für halbsymmetrische Graphen
   • Beweis einer äquivalenten Charakterisierung des Bipartiteness Ratio bezüglich guter Verbundenheit im Hilfsgraphen $G'$ (Satz 3.5)
   • Erweiterung des Cut-Matching-Game-Frameworks vom Sparsest Cut auf das Bipartiteness Ratio
3. Minimum-Uncut-Anwendung: Entwurf eines $\tilde{O}(mn)$-Zeit-Algorithmus, der für Graphen mit Minimum-Uncut-Ratio $\eta$ einen Schnitt mit Uncut-Ratio $O(\log n\log(1/\eta))\cdot\eta$ findet
4. Gerichtete Erweiterung:
   • Definition des gerichteten Bipartiteness Ratio und seiner Charakterisierung durch kleine Modulfunktionen
   • Realisierung einer $O(\log n)$-Approximation durch gerichtete $\ell_1$-Einbettung
   • Bereitstellung eines gerichteten Minimum-Uncut-Algorithmus

Methodische Details

Aufgabendefinition

$b$-Bipartiteness Ratio: Gegeben ein ungerichteter Graph $G=(V,E,w)$ und positive Knotengewichte $b:V\to\mathbb{Z}_{++}$, wird definiert: $\beta_b(G) := \min_{x\in\{0,\pm1\}^V\setminus\{0\}} \beta_b(x), \quad \beta_b(x) := \frac{\sum_{(i,j)\in E} w(i,j)\cdot|x_i+x_j|}{\sum_{i\in V} b(i)\cdot|x_i|}$

Eingabe: Graph $G$, Kantengewichte $w$, Knotengewichte $b$, Parameter $r>0$
Ausgabe: Vektor $x\in\{0,\pm1\}^V$ so dass $\beta_b(x)\leq O(\log n)\cdot\beta_b(G)$

Kern-Technologie-Framework

1. Hilfsgraph-Konstruktion

Konstruktion eines halbsymmetrischen bipartiten Graphen $G'=(V^+\cup V^-,E')$:

• $V^+,V^-$ sind zwei disjunkte Kopien von $V$
• Für jede Kante $(i,j)\in E$ werden Kanten $(i^+,j^-)$ und $(i^-,j^+)$ zu $E'$ hinzugefügt
• Kantengewichte und Knotengewichte werden geerbt

Schlüsseleigenschaft (Lemma 3.2): Für jeden $x\in\{0,\pm1\}^V$ entsprechend einer Drei-Partition $(L,R,Z)$, sei $S=L^+\cup R^-$, dann: $\beta_b(x) = \frac{w(E'(S,\bar{S}))}{b(S)}$

Daher: $\beta_b(G) = \min_{S=L^+\cup R^-, \text{ disjunkt }L,R\subseteq V} \frac{w(E'(S,\bar{S}))}{b(S)}$

2. Charakterisierung der guten Verbundenheit

Definition (Symmetrische Quell-Senken-Paare): $(A,B)$ wird als symmetrisch bezeichnet, wenn es disjunkte $L,R\subseteq V$ gibt so dass: $A = L^+\cup R^-, \quad B = L^-\cup R^+$

Definition 3.3 (Gute Verbundenheit): Ein symmetrisches Paar $(A,B)$ wird $r$-gut-verbunden genannt, wenn im Hilfsnetzwerk $\mathcal{N}_{A,B,r}$ ein gesättigter Fluss von $s^+$ zu $s^-$ existiert, wobei:

• Kantenkapazitäten: Kapazität von $s^+$ zu jedem Knoten $u$ in $A$ ist $b(u)$; ähnlich für $B$ zu $s^-$
• Kapazität von Kante $e$ in $E'$ ist $w(e)/r$

$G'$ wird $r$-gut-verbunden genannt, wenn alle symmetrischen Paare $r$-gut-verbunden sind.

Satz 3.5 (Kern-Charakterisierung): $\beta_b(G)\geq r$ genau dann, wenn $G'$ ist $r$-gut-verbunden.

Beweisskizze:

• (⇒) Wenn $\beta_b(G)\geq r$, dann für jedes symmetrische Paar $(A,B)$ ist der minimale $s^+$-$s^-$-Schnitt $\geq b(A)$, daher existiert nach dem Max-Flow-Min-Cut-Theorem ein gesättigter Fluss
• (⇐) Wenn ein symmetrisches Paar $(A,B)$ nicht $r$-gut-verbunden ist, dann entspricht der minimale Schnitt einer konsistenten Menge $S$ mit $w(E'(S,\bar{S}))/b(S)<r$

3. Cut-Matching-Game

Game-Framework (Algorithmus 1):

• Verwaltung: MMWU-Dichtematrix $X_t$, leerer Multigraph $H$
• Jede Runde:
  1. Cut-Spieler: Berechnung der (ungefähren) Gram-Zerlegung $\{v_i\}$ von $D_b^{-1/2}X_tD_b^{-1/2}$
  2. Stichprobenziehung eines Gaußschen Vektors $g\sim\mathcal{N}(0,I_n)$, Berechnung $\tilde{v}_i=\langle g,v_i\rangle$
  3. Setzen $L'=\{i:\tilde{v}_i>0\}$, $R'=\{i:\tilde{v}_i<0\}$, Auswahl des größeren als $L$, Setzen $(A,B)$ als entsprechendes symmetrisches Paar
  4. Überprüfung: Wenn $(A,B)$ nicht $r$-gut-verbunden ist, Rückgabe des minimalen Schnitts entsprechend $x$
  5. Matching-Spieler: Andernfalls Suche nach gesättigtem Fluss, Zerlegung in Pfad-Multiset $\mathcal{P}_t$, Bedarfsgraph ist $M_t$
  6. Aktualisierung $F_t = D_b^{-1/2}(D_{M_t}+A_{M_t})D_b^{-1/2}$, MMWU-Update durchführen
• Beendigung: Nach $T=O(\log^2 n)$ Runden Rückgabe $H=M_1\oplus\cdots\oplus M_T$

Schlüsselanalyse:

1. Breite: $F_t\preceq 4I$ (Lemma-Beweis)
2. Gewinn: $\langle F_t,X_t\rangle = \sum_{(i,j)\in M_t}\|v_i+v_j\|^2 \geq \Omega(1/\log n)$ (durch Gaußsche Projektion)
3. MMWU-Grenze (Lemma 3.7): $\lambda_{\min}\left(\sum_{t=1}^T F_t\right) \geq (1-\rho\delta)\sum_{t=1}^T\langle F_t,X_t\rangle - \frac{\ln n}{\delta}$
   Mit $\delta=O(1)$, $T=O(\log^2 n)$ erhalten wir $\lambda_{\min}\geq\Omega(\log n)$
4. Zertifikat: Lemma 3.9 beweist $\beta_b(H)=\Omega(\log n)$, da $H$ mit $O(T)$-Staueinbettung in $G$ eingebettet werden kann, erhalten wir $\beta_b(G)=\Omega(r/\log n)$

Technische Innovationspunkte

1. Nutzung der Halbsymmetrie: Durch die halbsymmetrische Struktur des Hilfsgraphen $G'$ wird das Drei-Partition-Problem in ein symmetrisches Quell-Senken-Fluss-Problem umgewandelt, dies ist die Schlüssel-Problemumformulierung
2. Konsistenter-Schnitt-Lemma (Lemma 3.4): Unter Verwendung der Halbsymmetrie und Lemma 2.5 wird bewiesen, dass immer ein konsistenter minimaler Schnitt gefunden werden kann, was die Analyse vereinfacht
3. Gaußsche Projektions-Technik:
   • Projektion der hochdimensionalen Gram-Zerlegung auf eine Dimension, Beibehaltung der Näherung von $\|v_i+v_j\|$ (Gleichung 3.6)
   • Lemma 3.8 verwendet Laurent-Massart-Grenze, um zu garantieren, dass $\sum b(i)|\tilde{v}_i|^2\geq 1/2$ mit konstanter Wahrscheinlichkeit erfüllt ist
4. Schnelle Gram-Zerlegung (Lemma 3.11): Durch JL-Dimensionsreduktion und abgeschnittene Taylor-Erweiterung wird die $O(n^3)$ exakte Zerlegung auf $\tilde{O}(\min\{b(V),n^2\})$ reduziert

Experimentelle Einrichtung

Theoretischer Algorithmus, kein experimenteller Teil

Dieses Paper ist ein rein theoretisches Algorithmen-Paper mit Hauptbeiträgen in:

1. Theoretische Garantien: $O(\log n)$-Approximationsverhältnis
2. Zeitkomplexitätsanalyse: $\tilde{O}(m)$ für ursprüngliches Bipartiteness Ratio
3. Theoretischer Vergleich mit bestehenden Methoden (Tabelle 1)

Experimentelle Ergebnisse

Zusammenfassung theoretischer Ergebnisse

Hauptsatz (Satz 3.12):

• Approximationsverhältnis: $O(\log n)$
• Zeitkomplexität:
  • $O(\log^3 n\cdot\max\{\log^2 n,\log b(V)\}\cdot\min\{b(V),n^2\})$ arithmetische Operationen
  • $O(\log^2 n)$ Single-Commodity-Maximalfluss-Berechnungen
• Erfolgswahrscheinlichkeit: $\geq 1-1/\text{poly}(n)$

Minimum-Uncut-Anwendung (Satz 4.1):

• Eingabe: Graph mit Minimum-Uncut-Ratio $\eta$
• Ausgabe: Schnitt mit Uncut-Ratio $\leq O(\log n\log(1/\eta))\cdot\eta$
• Zeit: $\tilde{O}(mn)$

Vergleichende Analyse (Tabelle 1):

Vorteile:

• Gegenüber spektralen Methoden Tre12, KLLO+13: Unabhängig von Eigenwerten, besseres Approximationsverhältnis
• Gegenüber SDP-Methoden GVY93, ACMM05: Obwohl das Approximationsverhältnis etwas schwächer ist, sinkt die Zeit von $\tilde{O}(m^\omega)$ auf $\tilde{O}(mn)$ ($\omega\approx 2.37$)

Erweiterung auf gerichtete Graphen

Gerichtetes Bipartiteness Ratio (Gleichung 1.3): $\beta_b(x) = \frac{\sum_{(i,j)\in E}\psi_{ij}(x)}{\sum_i b(i)|x_i|}, \quad \psi_{ij}(x)=\begin{cases}|x_i+x_j| & x_i\geq x_j\\ |x_i|+|x_j| & \text{andernfalls}\end{cases}$

Satz 1.3: Polynomielle Zeit $O(\log n)$-Approximationsalgorithmus durch:

1. Konstruktion eines halbsymmetrischen Hilfsgraphen $G'$
2. Lösung der gerichteten Halbmetrik-Relaxation (LP)
3. Gerichtete $\ell_1$-schwache Einbettung CMM06 zur Realisierung von $O(\log|V'|)=O(\log n)$-Approximation

Satz 1.4: $O(\log n\log(1/\eta))\cdot\eta$-Approximation für gerichtetes Minimum Uncut

Verwandte Arbeiten

Spektrale Graphentheorie

1. Cheeger-Ungleichung AM85; Alo86: Verbindung des zweiten kleinsten Eigenwertes $\lambda_2$ mit der Leitfähigkeit $\phi(G)$: $\frac{\lambda_2}{2}\leq\phi(G)\leq\sqrt{2\lambda_2}$
2. Duale Cheeger-Ungleichung Tre12; BJ13: Beziehung des in diesem Paper untersuchten Bipartiteness Ratio zum größten Eigenwert $\lambda_n$
3. Höherordnungsspektrale Methoden KLLO+13; GS11: Nutzung mehrerer Eigenwerte zur Verbesserung der Approximation

Sparsest-Cut-Algorithmen

1. Kombinatorische Methoden:
   • Cut-Matching-Game KRV06: $O(\log^2 n)$
   • Verbesserung OSVV08: $O(\log n)$
   • Optimal AK16: $O(\sqrt{\log n})$ durch MMWU
2. SDP-Methode ARV09: $O(\sqrt{\log n})$ durch Metrik-Einbettung
3. Gerichtete Graphen Lou10; LTW24: $O(\log n)$-Approximation für gerichteten Sparsest Cut

Max-Cut/Minimum Uncut

1. Approximationsalgorithmen:
   • GW-Algorithmus GW94: $0.878$-Approximation (SDP)
   • Spektrale Methoden Tre12; KLLO+13: Abhängig von Eigenwerten
   • SDP-Hierarchie GS11; ACMM05: Stärker aber langsamer
2. Beitrag dieses Papers: Erste Anwendung des Cut-Matching-Game auf Bipartiteness Ratio, Realisierung quasi-linearer Zeit

Schlussfolgerungen und Diskussion

Hauptschlussfolgerungen

1. Erste polynomielle Zeit $O(\log n)$-Approximationsalgorithmus für Bipartiteness Ratio
2. Einführung der guten Verbundenheit für halbsymmetrische Graphen, Etablierung neuer Fluss-Schnitt-Charakterisierung
3. Realisierung quasi-linearer Zeit $\tilde{O}(m)$, signifikante Verbesserung gegenüber SDP-Methoden
4. Erfolgreiche Erweiterung auf gerichtete Graphen, Bereitstellung eines einheitlichen Frameworks

Einschränkungen

1. Approximationsverhältnis: $O(\log n)$ schwächer als SDP's $O(\sqrt{\log n})$ ARV09; ACMM05
2. Minimum Uncut: Zusätzlicher $\log(1/\eta)$-Faktor, Lücke gegenüber ACMM05's $O(\sqrt{\log n})\cdot\eta$
3. Gerichtete Graphen-Zeit: Gerichtete Version benötigt immer noch polynomielle Zeit (nicht quasi-linear), abhängig von LP-Lösung
4. Praktische Leistung: Rein theoretische Ergebnisse, keine experimentelle Validierung

Zukünftige Richtungen

1. Verbesserung des Approximationsverhältnisses: Kann $O(\sqrt{\log n})$ erreicht werden und gleichzeitig quasi-lineare Zeit beibehalten?
2. Beschleunigung gerichteter Graphen: Kann die gerichtete Bipartiteness-Ratio-Approximation auch auf $\tilde{O}(m)$-Zeit reduziert werden?
3. Untergrenzen: Ist $O(\log n)$ eine inhärente Grenze für flussbasierte Methoden?
4. Praktische Anwendungen: Empirische Studien in Netzwerkanalyse und Gemeinschaftserkennung

Tiefgreifende Bewertung

Stärken

1. Theoretischer Durchbruch:
   • Lösung eines langfristigen offenen Problems (seit 2012 kein Approximationsalgorithmus)
   • Erste Etablierung der Äquivalenz zwischen Bipartiteness Ratio und guter Verbundenheit (Satz 3.5)
   • Elegante Vereinigung ungerichteter und gerichteter Fälle
2. Technische Innovationen:
   • Halbsymmetrie-Nutzung: Hilfsgraph-Konstruktion transformiert geschickt Drei-Partition in symmetrisches Fluss-Problem
   • MMWU-Analyse: Kreative Anwendung des AK16-Frameworks auf neues Problem, Gaußsche Projektions-Technik für Gram-Zerlegung
   • Schnelle Implementierung: Lemma 3.11's ungefähre Gram-Zerlegung vermeidet $O(n^3)$-Engpass
3. Algorithmen-Effizienz:
   • Zeitkomplexität $\tilde{O}(m)$ nahe optimal (Graphen-Eingabe erforderlich)
   • Nur Single-Commodity-Fluss, kann neueste quasi-lineare Algorithmen nutzen CKLP+22
   • Größenordnungs-Verbesserung gegenüber SDP-Methoden ($\tilde{O}(m^\omega)$)
4. Theoretische Vollständigkeit:
   • Strikte Wahrscheinlichkeitsanalyse (Lemma 3.8 nutzt Laurent-Massart-Grenze)
   • Detaillierte Zeitkomplexitäts-Zerlegung
   • Gerichtete Erweiterung demonstriert Framework-Universalität

Schwächen

1. Approximationsverhältnis-Lücke:
   • $O(\log n)$ vs. $O(\sqrt{\log n})$ ARV09: Zwar akzeptabel aber nicht optimal
   • Keine Diskussion über mögliche Verbesserungen (z.B. durch stärkere SDP-Relaxationen)
2. Fehlende Experimente:
   • Keine Leistungsbewertung auf echten Graphen
   • Keine Vergleiche von Konstanten-Faktoren (große O versteckt möglicherweise große Konstanten)
   • Fehlender empirischer Vergleich mit spektralen Methoden
3. Gerichtete Graphen nicht vollständig gelöst:
   • Zeitkomplexität der gerichteten Version unklar (Satz 1.3 sagt nur "polynomielle Zeit")
   • Benötigt LP-Lösung, möglicherweise langsamer als ungerichteter Fall
   • Keine Diskussion über Möglichkeit von $\tilde{O}(m)$
4. Technische Details:
   • Beweis von Lemma 3.11 im Anhang, Haupttext fehlt Intuition
   • Gaußsche Projektion benötigt $O(\log n)$ Resampling (Lemma 3.8), praktisch möglicherweise leistungsbeeinflussend
   • MMWU-Schrittweite $\delta$-Auswahl fehlt Anleitung
5. Anwendungs-Einschränkungen:
   • Zusätzlicher $\log(1/\eta)$-Faktor bei Minimum Uncut möglicherweise signifikant wenn $\eta$ sehr klein
   • Keine Diskussion über praktische Bedeutung der gewichteten Version ($b$ beliebig)

Einflussfähigkeit

1. Theoretische Beiträge:
   • Neue algorithmische Perspektive für Spektrale Graphentheorie
   • Konzept der guten Verbundenheit für halbsymmetrische Graphen möglicherweise unabhängig wertvoll
   • Demonstriert breitere Anwendbarkeit des Cut-Matching-Game
2. Technischer Einfluss:
   • MMWU+Gaußsche-Projektion-Paradigma möglicherweise auf andere Verhältnis-Probleme anwendbar
   • Schnelle Gram-Zerlegungstechnik (Lemma 3.11) wiederverwendbar
3. Praktischer Wert:
   • Quasi-lineare Zeit ermöglicht Verarbeitung großer Graphen
   • Könnte Anwendung von Bipartiteness Ratio in Netzwerkanalyse fördern
   • Gerichtete Version bietet Werkzeug für Gemeinschaftserkennung in gerichteten Graphen
4. Offene Probleme:
   • Inspiriert Forschung zur Verbesserung des Approximationsverhältnisses
   • Gerichtete Graphen-Beschleunigung hat klaren Wert

Anwendungsszenarien

1. Großskalige Graphen-Analyse:
   • Quasi-Bipartitäts-Erkennung in sozialen Netzwerken
   • Struktur-Analyse von Benutzer-Objekt-Graphen in Empfehlungssystemen
2. Spektrale Clusterung:
   • Als Clusterung-Methode basierend auf größtem Eigenwert
   • Gemeinschaftserkennung in vorzeichenbehafteten Graphen XOG20; NP22
3. Kombinatorische Optimierung:
   • Vorverarbeitung für Max-Cut (durch rekursive Bisection)
   • Heuristiken für Graphen-Partitionierungsprobleme
4. Theoretische Forschung:
   • Benchmark für Graphen-Parameter-Approximation
   • Neue Perspektive auf Fluss-Schnitt-Dualität

Nicht anwendbar: Szenarien, die $O(\sqrt{\log n})$-optimale Approximation benötigen (sollten SDP-Methoden verwenden)

Referenzen (Auswahl)

1. Tre12 L. Trevisan. "Max cut and the smallest eigenvalue". SIAM J. Comput. 41.6 (2012): Definiert Bipartiteness Ratio, beweist duale Cheeger-Ungleichung
2. KRV06 R. Khandekar, S. Rao, U. Vazirani. "Graph partitioning using single commodity flows". STOC 2006: Führt Cut-Matching-Game ein
3. AK16 S. Arora, S. Kale. "A combinatorial, primal-dual approach to semidefinite programs". J. ACM 63.2 (2016): MMWU-Framework, Haupttechnik-Grundlage dieses Papers
4. ACMM05 A. Agarwal et al. "$O(\sqrt{\log n})$ approximation algorithms for min uncut...". STOC 2005: SDP-Methode für Minimum Uncut, Hauptvergleich dieses Papers
5. CKLP+22 L. Chen et al. "Maximum flow and minimum-cost flow in almost-linear time". FOCS 2022: Quasi-lineare Zeit-Maximalfluss, ermöglicht Effizienz dieses Algorithmus

Gesamtbewertung: Dies ist ein hochqualitatives theoretisches Algorithmen-Paper, das ein langfristiges offenes Problem löst, mit signifikanten technischen Innovationen (Halbsymmetrie-Charakterisierung, MMWU-Erweiterung) und quasi-linearer Zeitkomplexität. Hauptmängel sind das nicht-optimale Approximationsverhältnis und fehlende experimentelle Validierung. Wichtiger Beitrag zur theoretischen Informatik-Gemeinschaft, könnte praktische Forschung zum Bipartiteness Ratio einleiten. Empfehlung zur Veröffentlichung in Top-Konferenzen (FOCS/SODA-Niveau).