انتشار المعتقدات لتدفق الشبكة بتكلفة دنيا: التقارب والدقة

نقوم بصياغة خوارزمية انتشار المعتقدات (BP) في سياق مشكلة تدفق الشبكة ذات التكلفة الدنيا مع قدرة معينة (ℳ ℱ). على عكس معظم الحالات التي تم دراستها سابقًا، فإن رسائل BP في سياق هذه المشكلة هي دوال خطية مقطعية. نثبت أن BP تتقارب نحو الحل الأمثل في وقت زمني كاذب متعدد الحدود، بشرط أن يكون الحل الأمثل فريدًا وأن تكون مدخلات المشكلة عددية. علاوة على ذلك، نقدم تعديلًا بسيطًا على خوارزمية BP الذي يوفر مخطط تقريب عشوائي متعدد الحدود بالكامل (FPRAS) لـ ℳ ℱ. هذه هي الحالة الأولى التي يُثبت فيها أن BP له وقت تشغيل كامل متعدد الحدود.