خوارزميات تقريب $O(\log n)$ لنسبة الثنائية

المعلومات الأساسية

• معرّف الورقة: 2507.12847
• العنوان: خوارزميات تقريب $O(\log n)$ لنسبة الثنائية
• المؤلفون: Tasuku Soma (معهد الإحصاء الرياضي وRIKEN AIP)، Mingquan Ye (المعهد الوطني للمعلوماتية وجامعة كاليفورنيا سانتا كروز)، Yuichi Yoshida (المعهد الوطني للمعلوماتية)
• التصنيف: cs.DS (هياكل البيانات والخوارزميات)
• تاريخ النشر: 5 نوفمبر 2025 (arXiv v2)
• رابط الورقة: https://arxiv.org/abs/2507.12847

الملخص

تقدم هذه الورقة أول خوارزمية تقريب $O(\log n)$ لنسبة الثنائية (bipartiteness ratio) في الرسوم البيانية غير الموجهة، حيث $n$ هو عدد الرؤوس. تعمل الطريقة على توسيع إطار عمل لعبة القطع-المطابقة من مشكلة القطع الأقل كثافة (sparsest cut) إلى مشكلة نسبة الثنائية، وتتطلب فقط $\text{polylog } n$ حسابات لتدفق أقصى أحادي السلعة غير موجه. بالجمع مع أسرع خوارزميات التدفق الأقصى غير الموجهة الحالية، يمكن تحقيق تعقيد زمني شبه خطي. يقدم البحث مفهوم الاتصال الجيد للرسوم البيانية شبه المتماثلة، ويثبت توصيفاً جديداً لنسبة الثنائية فيما يتعلق بالاتصال الجيد في الرسوم البيانية المساعدة شبه المتماثلة. كتطبيق، يقدم خوارزمية الحد الأدنى غير المقطوع (minimum uncut) بتعقيد زمني $\tilde{O}(mn)$. بالإضافة إلى ذلك، يعرّف نسبة الثنائية الموجهة ويقدم خوارزمية تقريب $O(\log n)$ من خلال تضمين نمط Leighton-Rao الموجه.

خلفية البحث والدافع

تعريف المشكلة

مشكلة نسبة الثنائية هي مشكلة تحسين نظرية الرسوم البيانية قدمها Trevisan Tre12. بالنسبة للرسم البياني غير الموجه $G=(V,E,w)$، يُعرّف: $\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|}$

تصف هذه النسبة مدى انحراف الرسم البياني عن كونه ثنائياً: $\beta(G)=0$ إذا وفقط إذا كان $G$ ثنائياً.

أهمية البحث

1. الأهمية النظرية: نسبة الثنائية هي مفهوم أساسي في عدم المساواة المزدوج لـ Cheeger، وترتبط ارتباطاً وثيقاً بأكبر قيمة ذاتية $\lambda_n$ لمصفوفة لابلاسيان المعيارية: $\frac{2-\lambda_n}{2} \leq \beta(G) \leq \sqrt{2(2-\lambda_n)}$
2. القيمة التطبيقية:
   • تصميم الخوارزميات الطيفية: استخدم Trevisan هذا عدم المساواة لتصميم خوارزمية طيفية نقية للقطع الأقصى
   • تحليل الشبكات: تطبيقات في تجميع الرسوم البيانية الموقعة واكتشاف المجتمعات XOG20; AL20; NP22
   • التحسين التوافقي: ارتباط وثيق بمشاكل القطع الأقصى والحد الأدنى غير المقطوع

قيود الطرق الموجودة

1. غياب خوارزميات التقريب: على الرغم من وجود خوارزميات تقريب ناضجة لعدم المساواة Cheeger والقطع الأقل كثافة (مثل تقريب $O(\sqrt{\log n})$)، لم تكن هناك أي خوارزمية تقريب زمنية متعددة الحدود لنسبة الثنائية
2. عدم كفاية الطرق الطيفية: الطرق الطيفية الموجودة (المستندة إلى المتجهات الذاتية) توفر فقط حدوداً نظرية ولا يمكنها حل مشكلة التحسين بشكل مباشر
3. الاختلاف عن القطع الأقل كثافة: على الرغم من أن نسبة الثنائية تشبه شكلياً القطع الأقل كثافة، فإن شروطها (بنية التقسيم الثلاثي) تجعل التطبيق المباشر للتقنيات الموجودة يواجه تحديات

دافع البحث

ملء الفراغ في خوارزميات التقريب لنسبة الثنائية، وتوفير أدوات خوارزمية جديدة لنظرية الرسوم البيانية الطيفية والتحسين التوافقي.

المساهمات الأساسية

1. أول خوارزمية تقريب: تقديم أول خوارزمية تقريب $O(\log n)$ لنسبة الثنائية $b$، بتعقيد زمني $\tilde{O}(\min\{b(V),n^2\}+m)$
2. الابتكارات النظرية:
   • إدخال مفهوم الاتصال الجيد (well-linkedness) للرسوم البيانية شبه المتماثلة
   • إثبات توصيف معادل لنسبة الثنائية فيما يتعلق بالاتصال الجيد في الرسم البياني المساعد $G'$ (النظرية 3.5)
   • توسيع إطار عمل لعبة القطع-المطابقة من القطع الأقل كثافة إلى نسبة الثنائية
3. تطبيق الحد الأدنى غير المقطوع: تصميم خوارزمية بتعقيد زمني $\tilde{O}(mn)$، والتي بالنسبة للرسوم البيانية ذات نسبة الحد الأدنى غير المقطوع $\eta$، تجد قطعاً بنسبة غير مقطوعة $O(\log n\log(1/\eta))\cdot\eta$
4. التوسيع الموجه:
   • تعريف نسبة الثنائية الموجهة وتوصيفها بالدوال شبه المعيارية
   • تحقيق تقريب $O(\log n)$ من خلال تضمين $\ell_1$ الموجه
   • توفير خوارزمية الحد الأدنى غير المقطوع الموجهة

شرح الطريقة

تعريف المهمة

نسبة الثنائية $b$: بالنسبة للرسم البياني غير الموجه $G=(V,E,w)$ وأوزان رؤوس موجبة $b:V\to\mathbb{Z}_{++}$، يُعرّف: $\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|}$

الإدخال: الرسم البياني $G$، أوزان الحواف $w$، أوزان الرؤوس $b$، المعامل $r>0$
الإخراج: متجه $x\in\{0,\pm1\}^V$ بحيث $\beta_b(x)\leq O(\log n)\cdot\beta_b(G)$

إطار العمل التقني الأساسي

1. بناء الرسم البياني المساعد

بناء رسم بياني ثنائي شبه متماثل $G'=(V^+\cup V^-,E')$:

• $V^+,V^-$ نسختان منفصلتان من $V$
• لكل حافة $(i,j)\in E$، أضف الحواف $(i^+,j^-)$ و$(i^-,j^+)$ إلى $E'$
• ورث أوزان الحواف وأوزان الرؤوس

الخاصية الرئيسية (اللمة 3.2): لأي $x\in\{0,\pm1\}^V$ يقابل التقسيم الثلاثي $(L,R,Z)$، دع $S=L^+\cup R^-$، إذن: $\beta_b(x) = \frac{w(E'(S,\bar{S}))}{b(S)}$

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

2. توصيف الاتصال الجيد

التعريف (أزواج المصدر والحوض المتماثلة): يُقال أن $(A,B)$ متماثل إذا كانت هناك $L,R\subseteq V$ منفصلة بحيث: $A = L^+\cup R^-, \quad B = L^-\cup R^+$

التعريف 3.3 (الاتصال الجيد): يُقال أن الزوج المتماثل $(A,B)$ هو $r$-متصل بشكل جيد إذا كان هناك تدفق مشبع من $s^+$ إلى $s^-$ في شبكة التدفق المساعدة $\mathcal{N}_{A,B,r}$، حيث:

• سعة الحافة: السعة من $s^+$ إلى كل رأس $u$ في $A$ هي $b(u)$؛ وبالمثل من $B$ إلى $s^-$
• سعة الحافة $e$ في $E'$ هي $w(e)/r$

يُقال أن $G'$ هو $r$-متصل بشكل جيد إذا كانت جميع الأزواج المتماثلة $r$-متصلة بشكل جيد.

النظرية 3.5 (التوصيف الأساسي): $\beta_b(G)\geq r$ إذا وفقط إذا كان $G'$ هو $r$-متصل بشكل جيد.

خطوط الإثبات:

• (⇒) إذا كان $\beta_b(G)\geq r$، فإن لأي زوج متماثل $(A,B)$، قيمة القطع الأدنى من $s^+$ إلى $s^-$ هي $\geq b(A)$، وبواسطة نظرية التدفق الأقصى والقطع الأدنى يوجد تدفق مشبع
• (⇐) إذا كان هناك زوج متماثل $(A,B)$ ليس $r$-متصل بشكل جيد، فإن القطع الأدنى المقابل للمجموعة المتسقة $S$ يرضي $w(E'(S,\bar{S}))/b(S)<r$

3. لعبة القطع-المطابقة

إطار عمل اللعبة (الخوارزمية 1):

• الصيانة: مصفوفة الكثافة MMWU $X_t$، رسم بياني متعدد فارغ $H$
• كل جولة:
  1. لاعب القطع: حساب تحليل Gram (تقريبي) لـ $D_b^{-1/2}X_tD_b^{-1/2}$ من $\{v_i\}$
  2. أخذ عينة من متجه غاوسي $g\sim\mathcal{N}(0,I_n)$، حساب $\tilde{v}_i=\langle g,v_i\rangle$
  3. دع $L'=\{i:\tilde{v}_i>0\}$، $R'=\{i:\tilde{v}_i<0\}$، خذ الأكبر كـ $L$، اضبط $(A,B)$ على الزوج المتماثل المقابل
  4. الحكم: إذا كان $(A,B)$ ليس $r$-متصل بشكل جيد، أرجع $x$ المقابل للقطع الأدنى
  5. لاعب المطابقة: وإلا، جد تدفقاً مشبعاً، حلله إلى مجموعة متعددة من المسارات $\mathcal{P}_t$، رسم الطلب هو $M_t$
  6. تحديث $F_t = D_b^{-1/2}(D_{M_t}+A_{M_t})D_b^{-1/2}$، إجراء تحديث MMWU
• الإنهاء: بعد $T=O(\log^2 n)$ جولة، أرجع $H=M_1\oplus\cdots\oplus M_T$

التحليل الرئيسي:

1. العرض: $F_t\preceq 4I$ (إثبات اللمة)
2. الكسب: $\langle F_t,X_t\rangle = \sum_{(i,j)\in M_t}\|v_i+v_j\|^2 \geq \Omega(1/\log n)$ (من خلال الإسقاط الغاوسي)
3. حد MMWU (اللمة 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}$
   بأخذ $\delta=O(1)$، $T=O(\log^2 n)$، نحصل على $\lambda_{\min}\geq\Omega(\log n)$
4. الشهادة: تثبت اللمة 3.9 أن $\beta_b(H)=\Omega(\log n)$، وبما أن $H$ يمكن أن تُضغط بشكل $O(T)$ إلى $G$، نحصل على $\beta_b(G)=\Omega(r/\log n)$

نقاط الابتكار التقني

1. استخدام شبه التماثل: من خلال بنية شبه التماثل للرسم البياني المساعد $G'$، تحويل مشكلة التقسيم الثلاثي إلى مشكلة تدفق أزواج مصدر-حوض متماثلة، وهذا هو إعادة صياغة المشكلة الرئيسية
2. لمة القطع المتسقة (اللمة 3.4): استخدام شبه التماثل واللمة 2.5، إثبات أنه يمكن دائماً العثور على قطع أدنى متسق، مما يبسط التحليل
3. تقنية الإسقاط الغاوسي:
   • إسقاط تحليل Gram عالي الأبعاد إلى بُعد واحد، الحفاظ على تقريب $\|v_i+v_j\|$ (الصيغة 3.6)
   • تستخدم اللمة 3.8 حد Laurent-Massart لضمان $\sum b(i)|\tilde{v}_i|^2\geq 1/2$ بحتمية ثابتة
4. تحليل Gram السريع (اللمة 3.11): من خلال تقليل الأبعاد JL وتوسيع Taylor المقطوع، تقليل تحليل $O(n^3)$ الدقيق إلى $\tilde{O}(\min\{b(V),n^2\})$

إعداد التجربة

خوارزمية نظرية، بدون جزء تجريبي

هذه ورقة خوارزمية نظرية بحتة، مع المساهمات الرئيسية في:

1. الضمانات النظرية: نسبة تقريب $O(\log n)$
2. تحليل التعقيد الزمني: $\tilde{O}(m)$ لنسبة الثنائية الأصلية
3. المقارنة النظرية مع الطرق الموجودة (الجدول 1)

نتائج التجربة

ملخص النتائج النظرية

النظرية الرئيسية (النظرية 3.12):

• نسبة التقريب: $O(\log n)$
• التعقيد الزمني:
  • $O(\log^3 n\cdot\max\{\log^2 n,\log b(V)\}\cdot\min\{b(V),n^2\})$ عملية حسابية
  • $O(\log^2 n)$ حسابات تدفق أقصى أحادي السلعة
• احتمالية النجاح: $\geq 1-1/\text{poly}(n)$

تطبيق الحد الأدنى غير المقطوع (النظرية 4.1):

• الإدخال: رسم بياني بنسبة حد أدنى غير مقطوع $\eta$
• الإخراج: قطع بنسبة غير مقطوعة $\leq O(\log n\log(1/\eta))\cdot\eta$
• الوقت: $\tilde{O}(mn)$

تحليل المقارنة (الجدول 1):

المزايا:

• مقارنة بالطرق الطيفية Tre12, KLLO+13: لا تعتمد على القيم الذاتية، نسبة تقريب أفضل
• مقارنة بطرق SDP GVY93, ACMM05: على الرغم من أن نسبة التقريب أضعف قليلاً، لكن الوقت ينخفض من $\tilde{O}(m^\omega)$ إلى $\tilde{O}(mn)$ ($\omega\approx 2.37$)

التوسيع للرسوم البيانية الموجهة

نسبة الثنائية الموجهة (الصيغة 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{خلاف ذلك}\end{cases}$

النظرية 1.3: خوارزمية تقريب $O(\log n)$ في الوقت متعدد الحدود، من خلال:

1. بناء رسم بياني أداة شبه متماثل موجه $G'$
2. حل استرخاء شبه المقياس الموجه (LP)
3. تضمين $\ell_1$ الموجه الضعيف CMM06 لتحقيق تقريب $O(\log|V'|)=O(\log n)$

النظرية 1.4: تقريب $O(\log n\log(1/\eta))\cdot\eta$ للحد الأدنى غير المقطوع الموجه

الأعمال ذات الصلة

نظرية الرسوم البيانية الطيفية

1. عدم المساواة Cheeger AM85; Alo86: ربط القيمة الذاتية الثانية الأصغر $\lambda_2$ بالموصلية $\phi(G)$: $\frac{\lambda_2}{2}\leq\phi(G)\leq\sqrt{2\lambda_2}$
2. عدم المساواة المزدوج Cheeger Tre12; BJ13: العلاقة بين نسبة الثنائية المدروسة في هذه الورقة والقيمة الذاتية الأكبر $\lambda_n$
3. طرق طيفية من الدرجة الأعلى KLLO+13; GS11: استخدام قيم ذاتية متعددة لتحسين التقريب

خوارزميات القطع الأقل كثافة

1. طرق توافقية:
   • لعبة القطع-المطابقة KRV06: $O(\log^2 n)$
   • تحسين OSVV08: $O(\log n)$
   • أمثل AK16: $O(\sqrt{\log n})$ من خلال MMWU
2. طريقة SDP ARV09: $O(\sqrt{\log n})$ من خلال تضمين المقياس
3. الرسوم البيانية الموجهة Lou10; LTW24: تقريب $O(\log n)$ للقطع الأقل كثافة الموجه

القطع الأقصى/الحد الأدنى غير المقطوع

1. خوارزميات التقريب:
   • خوارزمية GW GW94: تقريب $0.878$ (SDP)
   • طرق طيفية Tre12; KLLO+13: تعتمد على القيم الذاتية
   • تسلسل هرمي SDP GS11; ACMM05: أقوى لكن أبطأ
2. مساهمة هذه الورقة: أول تطبيق لعبة القطع-المطابقة على نسبة الثنائية، تحقيق وقت شبه خطي

الخلاصة والنقاش

الاستنتاجات الرئيسية

1. توفير أول خوارزمية تقريب زمنية متعددة الحدود $O(\log n)$ لنسبة الثنائية
2. إدخال الاتصال الجيد للرسوم البيانية شبه المتماثلة، إنشاء توصيف تدفق-قطع جديد
3. تحقيق وقت شبه خطي $\tilde{O}(m)$، تحسن كبير عن طرق SDP
4. توسيع ناجح للرسوم البيانية الموجهة، توفير إطار عمل موحد

القيود

1. نسبة التقريب: $O(\log n)$ أضعف من $O(\sqrt{\log n})$ لـ SDP ARV09; ACMM05
2. الحد الأدنى غير المقطوع: عامل إضافي $\log(1/\eta)$، فجوة مقارنة بـ ACMM05 بـ $O(\sqrt{\log n})\cdot\eta$
3. وقت الرسوم البيانية الموجهة: النسخة الموجهة تتطلب وقتاً متعدد الحدود (لم تصل إلى شبه خطي)، تعتمد على حل LP
4. الأداء العملي: نتائج نظرية بحتة، بدون تحقق تجريبي

الاتجاهات المستقبلية

1. تحسين نسبة التقريب: هل يمكن تحقيق $O(\sqrt{\log n})$ مع الحفاظ على الوقت شبه الخطي؟
2. تسريع الرسوم البيانية الموجهة: هل يمكن تقليل تقريب نسبة الثنائية الموجهة إلى وقت $\tilde{O}(m)$؟
3. الحدود الدنيا: هل $O(\log n)$ هو حد متأصل للطرق المستندة إلى التدفق؟
4. التطبيقات العملية: دراسات تجريبية في تحليل الشبكات واكتشاف المجتمعات

التقييم المتعمق

المزايا

1. اختراق نظري:
   • حل مشكلة مفتوحة طويلة الأمد (بدون خوارزميات تقريب منذ 2012)
   • أول توصيف يربط نسبة الثنائية بالاتصال الجيد (النظرية 3.5)
   • توحيد أنيق للحالات غير الموجهة والموجهة
2. الابتكار التقني:
   • استخدام شبه التماثل: بناء الرسم البياني المساعد يحول بذكاء التقسيم الثلاثي إلى مشكلة تدفق متماثلة
   • تحليل MMWU: تطبيق إبداعي لإطار عمل AK16 على مشكلة جديدة، تقنية الإسقاط الغاوسي تتعامل مع تحليل Gram
   • التنفيذ السريع: اللمة 3.11 لتحليل Gram التقريبي تتجنب اختناق $O(n^3)$
3. كفاءة الخوارزمية:
   • التعقيد الزمني $\tilde{O}(m)$ قريب من الأمثل (يتطلب قراءة الرسم البياني)
   • يتطلب فقط تدفق أحادي السلعة، يمكن الاستفادة من أحدث خوارزميات التدفق الأقصى شبه الخطية CKLP+22
   • مقارنة بطرق SDP ($\tilde{O}(m^\omega)$) تحسن بعدة رتب من حيث الحجم
4. الاكتمال النظري:
   • تحليل احتمالي صارم (اللمة 3.8 تستخدم حد Laurent-Massart)
   • تحليل تفصيلي لتعقيد الوقت
   • التوسيع الموجه يوضح عمومية الإطار

أوجه القصور

1. فجوة نسبة التقريب:
   • $O(\log n)$ مقابل $O(\sqrt{\log n})$ ARV09: مقبول لكن ليس أمثل
   • لم يناقش ما إذا كان التحسين ممكناً (مثل من خلال استرخاء SDP أقوى)
2. غياب التجارب:
   • لا تقييم أداء على رسوم بيانية حقيقية
   • لم تقارن العوامل الثابتة (قد تكون الثوابت المخفية في O الكبير كبيرة جداً)
   • نقص المقارنة التجريبية مع الطرق الطيفية
3. الرسوم البيانية الموجهة لم تُحل بالكامل:
   • التعقيد الزمني للنسخة الموجهة غير واضح (النظرية 1.3 تقول فقط "وقت متعدد الحدود")
   • يتطلب حل LP، قد يكون أبطأ من الحالة غير الموجهة
   • لم يناقش ما إذا كان يمكن تحقيق $\tilde{O}(m)$
4. تفاصيل تقنية:
   • إثبات اللمة 3.11 في الملحق، الورقة الرئيسية تفتقد الحدس
   • الإسقاط الغاوسي يتطلب $O(\log n)$ إعادة أخذ عينات (اللمة 3.8)، قد يؤثر على الأداء العملية
   • اختيار خطوة MMWU $\delta$ يفتقد التوجيه
5. قيود التطبيق:
   • عامل إضافي $\log(1/\eta)$ للحد الأدنى غير المقطوع قد يكون كبيراً عندما يكون $\eta$ صغيراً جداً
   • لم يناقش الأهمية العملية للنسخة الموزونة ($b$ تعسفي)

التأثير

1. المساهمة النظرية:
   • توفير منظور خوارزمي جديد لنظرية الرسوم البيانية الطيفية
   • مفهوم الاتصال الجيد للرسوم البيانية شبه المتماثلة قد يكون له قيمة مستقلة
   • إظهار قابلية تطبيق أوسع لعبة القطع-المطابقة
2. التأثير التقني:
   • نمط MMWU + الإسقاط الغاوسي قد ينطبق على مشاكل نسبة أخرى
   • تقنية تحليل Gram السريع (اللمة 3.11) قابلة لإعادة الاستخدام
3. القيمة العملية:
   • الوقت شبه الخطي يجعل معالجة الرسوم البيانية الكبيرة ممكنة
   • قد يعزز تطبيق نسبة الثنائية في تحليل الشبكات
   • النسخة الموجهة توفر أداة لاكتشاف المجتمعات في الرسوم البيانية الموجهة
4. المشاكل المفتوحة:
   • تحفيز البحث لتحسين نسبة التقريب
   • مشكلة تسريع الرسوم البيانية الموجهة لها قيمة واضحة

السيناريوهات المعمول بها

1. تحليل الرسوم البيانية الكبيرة:
   • كشف شبه الثنائية في الشبكات الاجتماعية
   • تحليل البنية في رسوم بيانية المستخدم-العنصر لأنظمة التوصية
2. التجميع الطيفي:
   • كطريقة تجميع قائمة على أكبر قيمة ذاتية
   • اكتشاف المجتمعات في الرسوم البيانية الموقعة XOG20; NP22
3. التحسين التوافقي:
   • معالجة مسبقة للقطع الأقصى (من خلال التقسيم الثنائي العودي)
   • استكشاف إرشادي لمشاكل تقسيم الرسوم البيانية
4. البحث النظري:
   • معيار لتقريب معاملات الرسوم البيانية
   • منظور جديد على ثنائية التدفق-القطع

غير معمول به: السيناريوهات التي تتطلب تقريب $O(\sqrt{\log n})$ أمثل (يجب استخدام طرق SDP)

المراجع (مختارة)

1. Tre12 L. Trevisan. "Max cut and the smallest eigenvalue". SIAM J. Comput. 41.6 (2012): تعريف نسبة الثنائية، إثبات عدم المساواة المزدوج Cheeger
2. KRV06 R. Khandekar, S. Rao, U. Vazirani. "Graph partitioning using single commodity flows". STOC 2006: تقديم لعبة القطع-المطابقة
3. AK16 S. Arora, S. Kale. "A combinatorial, primal-dual approach to semidefinite programs". J. ACM 63.2 (2016): إطار عمل MMWU، الأساس التقني الرئيسي لهذه الورقة
4. ACMM05 A. Agarwal et al. "$O(\sqrt{\log n})$ approximation algorithms for min uncut...". STOC 2005: طريقة SDP للحد الأدنى غير المقطوع، المقارنة الرئيسية لهذه الورقة
5. CKLP+22 L. Chen et al. "Maximum flow and minimum-cost flow in almost-linear time". FOCS 2022: تدفق أقصى شبه خطي، يجعل خوارزمية هذه الورقة فعالة

التقييم الإجمالي: هذه ورقة خوارزمية نظرية عالية الجودة، تحل مشكلة مفتوحة طويلة الأمد، مع ابتكار تقني كبير (توصيف الرسوم البيانية شبه المتماثلة، توسيع MMWU)، وتحقق تعقيداً زمنياً شبه خطياً. أوجه القصور الرئيسية تكمن في عدم تحقيق نسبة التقريب الأمثل وغياب التحقق التجريبي. تساهم بشكل كبير في مجتمع علوم الحاسوب النظرية، وقد تفتح أبواباً لأبحاث تطبيقية حول نسبة الثنائية. يُوصى بالنشر في مؤتمرات من الدرجة الأولى (مستوى FOCS/SODA).