خوارزميات التقريب عن طريق تقسيم واحتلال عبر مؤشرات الانتشار

نقدم نموذجًا جديدًا لتقسيم واحتلال لتقريب مشاكل تحسين الرسوم البيانية NP-hard. يُنَمذج هذا النموذج مشاكل تحسين الرسوم البيانية التي تلبي خاصيتين: أولاً، يمكن تطبيق نهج التقسيم والاحتلال. ثانيًا، يمكن حساب مؤشر الانتشار الكسري في وقت كثيرات الحدود. يُعيّن مؤشر الانتشار أطوالًا إما للحواف أو للرؤوس في الرسم البياني المدخل، بحيث تكون جميع الرسميات الفرعية التي تكون فيها مشكلة التحسين غير تافهة ذات أقطار كبيرة. بالإضافة إلى ذلك، يوفر مؤشر الانتشار حَدًّا أدنى، τ، على تكلفة حل مشكلة التحسين. نقدم خوارزمية تقريبية في وقت كثيرات الحدود للمشاكل التي تم نمذجتها بواسطة نموذجنا، حيث يُعبر عامل التقريب عن O (minlog τ، log log τ، log k log log k) حيث k يرمز إلى عدد الرؤوس