تحليل الهيمنة

يُعد تحليل الهيمنة لخوارزمية تقريبية طريقةً لتقدير أدائها، وقد قدّمها غلوفر وبونين عام ١٩٩٧. على عكس تحليل نسبة التقريب التقليدي ، الذي يقارن الجودة العددية للحل المحسوب بالحل الأمثل، يتضمن تحليل الهيمنة فحص ترتيب الحل المحسوب ضمن الترتيب المُرتب لجميع الحلول الممكنة. في هذا النوع من التحليل، يُقال إن للخوارزمية عدد هيمنة أو عدد هيمنة K ، إذا وُجدت مجموعة فرعية من K حلًا مختلفًا للمسألة يكون ناتج الخوارزمية هو الأفضل بينها. يمكن أيضًا التعبير عن تحليل الهيمنة باستخدام نسبة الهيمنة ، وهي نسبة مساحة الحلول التي لا تتفوق على الحل المُعطى؛ يقع هذا العدد دائمًا ضمن الفترة [٠، ١]، حيث تشير الأعداد الأكبر إلى حلول أفضل. يُطبّق تحليل الهيمنة غالبًا على المسائل التي يكون فيها العدد الإجمالي للحلول الممكنة معروفًا، والتي يصعب إيجاد حل دقيق لها.

على سبيل المثال، في مسألة البائع المتجول ، يوجد ( n -1)! حلًا ممكنًا لمسألة تتضمن n مدينة. إذا أمكن إثبات أن خوارزمية ما تتمتع بعدد هيمنة قريب من ( n -1)!، أو ما يعادله، بنسبة هيمنة قريبة من 1، فيمكن اعتبارها أفضل من خوارزمية ذات عدد هيمنة أقل.

إذا أمكن إيجاد عينات عشوائية بكفاءة من فضاء حلول مسألة ما، كما هو الحال في مسألة البائع المتجول، فسيكون من السهل على خوارزمية عشوائية إيجاد حل ذي احتمالية عالية ونسبة هيمنة عالية: ببساطة، يتم إنشاء مجموعة من العينات واختيار أفضل حل من بينها. (انظر، على سبيل المثال، أورلين وشارما).

لا ينبغي الخلط بين رقم الهيمنة الموصوف هنا ورقم الهيمنة للرسم البياني، والذي يشير إلى عدد الرؤوس في أصغر مجموعة مهيمنة للرسم البياني.

ظهرت مؤخراً أعداد متزايدة من المقالات التي تستخدم تحليل الهيمنة لتقييم أداء الطرق الاستدلالية. ويمكن اعتبار هذا النوع من التحليل منافساً لتحليل نسبة التقريب التقليدي، كما يمكن اعتبارهما متكاملين.

يحتوي هذا القسم على مسح فني للنتائج المعروفة.

عدم التقريب. ليكن ε > 0. ما لم يكن P=NP ، فلا توجد خوارزمية متعددة الحدود لتغطية الرؤوس بحيث يكون عدد هيمنتها أكبر من 3^((nn^ε)/3).

عدم إمكانية التقريب. ليكن ε > 0. ما لم يكن P=NP، فلا توجد خوارزمية متعددة الحدود لمسألة حقيبة الظهر. بحيث يكون عدد هيمنتها أكبر من 2^(nn^ε).

• جلوفر، ف. وبونين، أ.ب. (1997). "مسألة البائع المتجول: حالات جديدة قابلة للحل وروابط مع تطوير خوارزميات التقريب". مجلة جمعية بحوث العمليات ، 48 (5): 502-510 . doi : 10.1057/palgrave.jors.2600392 . S2CID 123498731 . {{cite journal}}: صيانة CS1: أسماء متعددة: قائمة المؤلفين ( رابط )
• غوتين، غريغوري ويو، أندرس (2004). "مقدمة في تحليل الهيمنة" (ملف PDF) . التحسين عبر الإنترنت.{{cite web}}: صيانة CS1: أسماء متعددة: قائمة المؤلفين ( رابط )
• أورلين، جيمس ب. وشارما، دوشيانت (2002). "الجوار الممتد: التعريف والخصائص" (PDF) .{{cite web}}: صيانة CS1: أسماء متعددة: قائمة المؤلفين ( رابط )