مخطط تقريبي متعدد الحدود

تتمثل إحدى المشكلات العملية في خوارزميات PTAS في أن أسّ متعددة الحدود قد يزداد بشكل كبير مع انخفاض قيمة ε، على سبيل المثال إذا كان زمن التشغيل O ( n ^(1/ε)! ) . إحدى طرق معالجة هذه المشكلة هي تعريف مخطط تقريب متعدد الحدود الفعال ( EPTAS) ، حيث يُشترط أن يكون زمن التشغيل O ( nc ⁾ لثابت c مستقل عن ε . يضمن هذا أن يكون لزيادة حجم المسألة التأثير النسبي نفسه على زمن التشغيل بغض النظر عن قيمة ε المستخدمة؛ ومع ذلك، يمكن أن يعتمد الثابت في حالة Big-O على ε بشكل عشوائي. بعبارة أخرى، يعمل مخطط EPTAS في زمن FPT حيث يكون المعامل هو ε.

أما الأكثر تقييدًا، والأكثر فائدة من الناحية العملية، فهو مخطط التقريب متعدد الحدود بالكامل أو FPTAS ، والذي يتطلب أن تكون الخوارزمية متعددة الحدود في كل من حجم المشكلة n و 1/ε .

ما لم يكن P = NP ، فإنه يتحقق أن FPTAS ⊊ PTAS ⊊ APX . ^{[ 2 ]} وبالتالي، في ظل هذا الافتراض، فإن مسائل APX-hard لا تحتوي على PTASs.

يُعدّ مخطط التقريب شبه متعدد الحدود (QPTAS ) أحد المتغيرات الحتمية الأخرى لخوارزمية التقريب متعددة الحدود (PTAS) . يتميز QPTAS بتعقيد زمني قدره n ^{polylog ( n )} لكل قيمة ثابتة ε > 0. علاوة على ذلك، يمكن تشغيل PTAS في زمن FPT لبعض معلمات المسألة، مما يؤدي إلى مخطط تقريب مُعَلم .

قد تقبل بعض المسائل التي لا تمتلك خوارزمية تقريبية متعددة الحدود (PTAS) خوارزمية عشوائية ذات خصائص مشابهة، وهي مخطط تقريبي عشوائي متعدد الحدود (PRAS) . خوارزمية PRAS هي خوارزمية تأخذ مثالًا لمسألة تحسين أو عد، ومعاملًا ε > 0 ، وتُنتج، في زمن متعدد الحدود، حلًا باحتمالية عالية أن يكون ضمن عامل ε من الحل الأمثل. تقليديًا، تعني "الاحتمالية العالية" احتمالية أكبر من 3/4، مع أن التعريف، كما هو الحال مع معظم فئات التعقيد الاحتمالي، يبقى ثابتًا في مواجهة التغيرات في هذه القيمة الدقيقة (الحد الأدنى المطلوب عادةً ما يكون أكبر من 1/2). وكما هو الحال مع خوارزمية PTAS، يجب أن يكون زمن تشغيل خوارزمية PRAS متعدد الحدود في n ، ولكن ليس بالضرورة في ε . مع فرض قيود إضافية على وقت التشغيل في ε ، يمكن تعريف مخطط تقريب عشوائي فعال متعدد الحدود أو EPRAS مشابه لـ EPTAS، ومخطط تقريب عشوائي كامل متعدد الحدود أو FPRAS مشابه لـ FPTAS. ^{[ 3 ]}