الاختزال الحافظ على التقريب

يُعدّ الاختزال الصارم أبسط أنواع الاختزال الذي يحافظ على التقريب. في الاختزال الصارم، يجب ألا تتجاوز نسبة تقريب الحل y' للحالة x' من المسألة B نسبة تقريب الحل y للحالة x من المسألة A. بعبارة أخرى:

${\displaystyle R_{A}(x,y)\leq R_{B}(x',y')}$ل${\displaystyle x'=f(x),y=g(y')}$.

الاختزال الصارم هو الأكثر مباشرة: إذا كان هناك اختزال صارم من المشكلة أ إلى المشكلة ب، فيمكن دائمًا تقريب المشكلة أ بنسبة جيدة على الأقل مثل المشكلة ب. يحافظ الاختزال الصارم على العضوية في كل من PTAS و APX.

يوجد مفهوم مشابه للاختزال S، والذي${\displaystyle c_{A}(x,y)=c_{B}(x',y')}$ويجب أن تتساوى تكلفة الحل الأمثل للحالتين المتناظرتين. يُعدّ الاختزال من النوع S حالةً خاصةً جدًا من الاختزال الصارم، وهو أكثر تقييدًا. في الواقع، يجب أن تكون المسألتان A وB متطابقتين تمامًا تقريبًا. إن وجود اختزال من النوع S لا يعني فقط وجود اختزال صارم، بل يعني أيضًا وجود كل اختزال آخر مذكور هنا.

تحافظ اختزالات L على الانتماء إلى خوارزمية PTAS وكذلك خوارزمية APX (ولكن فقط لمسائل التصغير في حالة الأخيرة ). ونتيجة لذلك، لا يمكن استخدامها بشكل عام لإثبات نتائج الاكتمال المتعلقة بخوارزميات APX أو Log-APX أو Poly-APX، ولكن مع ذلك فهي ذات قيمة لصياغتها الطبيعية وسهولة استخدامها في البراهين. ^{[ 1 ]}

يُعدّ اختزال PTAS أحد أساليب الاختزال الشائعة الأخرى. ورغم أنه يحافظ على الانتماء إلى PTAS، إلا أنه لا يفعل ذلك بالنسبة لـ APX. ومع ذلك، يُعرَّف اكتمال APX بدلالة اختزالات PTAS.

تعتبر اختزالات PTAS تعميمًا لاختزالات P، الموضحة أدناه، مع الاختلاف الوحيد في أن الدالة g مسموح لها بالاعتماد على نسبة التقريب r .

يُعدّ كلٌّ من اختزال A واختزال P من أساليب الاختزال المتشابهة التي يمكن استخدامها لإثبات الانتماء إلى APX وPTAS على التوالي. يُقدّم كلا الأسلوبين دالةً جديدةً c ، مُعرّفةً على أعداد أكبر من 1، ويجب أن تكون قابلةً للحساب.

في اختزال A، لدينا ذلك

${\displaystyle R_{B}(x',y')\leq r\rightarrow R_{A}(x,y)\leq c(r)}$.

في عملية اختزال P، لدينا ذلك

${\displaystyle R_{B}(x',y')\leq c(r)\rightarrow R_{A}(x,y)\leq r}$.

إن وجود اختزال P يستلزم وجود اختزال PTAS.

يُعدّ الاختزال E، وهو تعميم للاختزال الصارم ولكنه يستلزم كلاً من الاختزال A والاختزال P، مثالاً على أسلوب اختزال أقل تقييدًا يحافظ على الانتماء ليس فقط إلى PTAS و APX، بل أيضًا إلى الفئات الأكبر Log-APX و Poly-APX . يُدخل الاختزال E مُعاملين جديدين، وهما متعدد الحدود p وثابت.${\displaystyle \beta }$تعريفها كالتالي.

في اختزال E، لدينا أنه بالنسبة لبعض كثيرات الحدود p وثابت${\displaystyle \beta }$،

• ${\displaystyle c_{B}({\text{OPT}}_{B}(x'))\leq p(|x|)c_{A}({\text{OPT}}_{A}(x))}$، أين${\displaystyle |x|}$يشير إلى حجم وصف حالة المشكلة.
• لأي حل${\displaystyle y'}$إلى B ، لدينا${\displaystyle R_{A}(x,y)\leq 1+\beta \cdot (R_{B}(x',y')-1)}$.

للحصول على اختزال من النوع A من اختزال من النوع E، دع${\displaystyle c(r)=1+\beta \cdot (r-1)}$وللحصول على اختزال P من اختزال E، دع${\displaystyle c(r)=1+(r-1)/\beta }$.

تُستخدم اختزالات AP لتحديد الاكتمال في فئتي Log-APX و Poly-APX . وهي حالة خاصة من اختزال PTAS، وتستوفي القيود التالية.

في اختزال AP، لدينا أنه بالنسبة لبعض الثوابت${\displaystyle \alpha }$،

${\displaystyle R_{B}(x',y')\leq r\rightarrow R_{A}(x,y)\leq 1+\alpha \cdot (r-1)}$

مع التعميم الإضافي الذي يسمح للدالة g بالاعتماد على نسبة التقريب r ، كما هو الحال في اختزال PTAS.

يُعدّ اختزال AP تعميمًا لاختزال E. ويتطلب اختزال AP فرض قيد إضافي للحفاظ على عضوية Log-APX و Poly-APX، كما هو الحال في اختزال E: بالنسبة لحجم مسألة ثابت، يجب ألا يتزايد وقت حساب f و g مع زيادة نسبة التقريب.

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