خوارزمية التقريب

الموسوعة الحرة

في علوم الحاسوب وبحوث العمليات ، تُعدّ خوارزميات التقريب خوارزميات فعّالة لإيجاد حلول تقريبية لمسائل التحسين (وخاصةً المسائل الصعبة من نوع NP ) مع ضمانات قابلة للإثبات بشأن بُعد الحل المُعاد عن الحل الأمثل. [ 1 ] تنشأ خوارزميات التقريب بشكل طبيعي في مجال علوم الحاسوب النظرية كنتيجة لفرضية P ≠ NP الشائعة . وبموجب هذه الفرضية، لا يمكن حلّ فئة واسعة من مسائل التحسين بدقة في وقت متعدد الحدود . ولذلك، يسعى مجال خوارزميات التقريب إلى فهم مدى إمكانية تقريب الحلول المثلى لهذه المسائل في وقت متعدد الحدود. في الغالبية العظمى من الحالات، يكون ضمان هذه الخوارزميات ضربيًا، ويُعبّر عنه بنسبة تقريب أو عامل تقريب، أي أن الحل الأمثل مضمون دائمًا أن يكون ضمن عامل ضربي (مُحدد مسبقًا) من الحل المُعاد. ومع ذلك، توجد أيضًا العديد من خوارزميات التقريب التي تُقدّم ضمانًا جمعيًا على جودة الحل المُعاد. من الأمثلة على خوارزميات التقريب ذات الضمان المضاعف خوارزمية كريستوفيدس-سيرديوكوف لمسألة البائع المتجول . فهي توفر مسارًا للبائع المتجول بمقياس طوله لا يتجاوز 3/2 من طول أقصر مسار مماثل. ومن الأمثلة الكلاسيكية على خوارزميات التقريب ذات الضمان الجمعي البرهان البنائي لنظرية فيزينغ . إذ يوضح كيفية تلوين حواف الرسم البياني غير الموجه بأطوال لا تتجاوز .Δ+1{\displaystyle \Delta +1}الألوان، أينΔ{\displaystyle \Delta }يمثل الحد الأقصى لدرجة أي عقدة. وبما أن كل حافة متصلة بعقدة ذات درجة قصوى يجب أن يكون لها لون مختلف، فإن البرهان البنائي للنظرية يُعطي خوارزمية ذات زمن متعدد الحدود تستخدم لونًا إضافيًا واحدًا على الأكثر عن الحد الأدنى المطلوب. ومن الأمثلة البارزة على خوارزمية تقريبية تُوفر كلا الأمرين ، خوارزمية التقريب الكلاسيكية لـ Lenstra و Shmoys و Tardos [ 2 ] لجدولة المهام على أجهزة متوازية غير مترابطة.

يتضمن تصميم وتحليل خوارزميات التقريب بشكل أساسي برهانًا رياضيًا يُثبت جودة الحلول المُعادة في أسوأ الحالات. [ 1 ] وهذا ما يميزها عن الطرق الاستدلالية مثل خوارزميات التلدين أو الخوارزميات الجينية ، التي تجد حلولًا جيدة نسبيًا لبعض المدخلات، ولكنها لا تُقدم مؤشرًا واضحًا في البداية حول متى قد تنجح أو تفشل.

هناك اهتمام واسع النطاق في علوم الحاسوب النظرية لفهم حدود تقريب بعض مسائل التحسين الشهيرة. على سبيل المثال، من الأسئلة المفتوحة التي ظلت مطروحة لفترة طويلة في علوم الحاسوب تحديد ما إذا كانت هناك خوارزمية تتفوق على تقريب 2 لمسألة غابة شتاينر التي وضعها أغراوال وآخرون [ 3 ] . وينبع الدافع وراء الرغبة في فهم مسائل التحسين المعقدة من منظور التقريب من اكتشاف روابط رياضية مدهشة وتقنيات قابلة للتطبيق على نطاق واسع لتصميم خوارزميات لهذه المسائل. ومن الأمثلة المعروفة على ذلك خوارزمية غومانز-ويليامسون للقطع الأقصى ، التي تحل مسألة في نظرية الرسوم البيانية باستخدام برنامج شبه محدد من المستوى الأول لتسلسل مجموع المربعات [ 4 ] .

مقدمة

من الأمثلة البسيطة على خوارزميات التقريب خوارزمية مسألة تغطية الرؤوس الدنيا ، حيث يكمن الهدف في اختيار أصغر مجموعة من الرؤوس بحيث يحتوي كل ضلع في الرسم البياني المُدخل على رأس واحد على الأقل من الرؤوس المختارة. إحدى طرق إيجاد تغطية للرؤوس هي تكرار العملية التالية: إيجاد ضلع غير مغطى، إضافة طرفيه إلى التغطية، ثم إزالة جميع الأضلاع المتصلة بأي من هذين الرأسين من الرسم البياني. بما أن أي تغطية للرؤوس في الرسم البياني المُدخل يجب أن تستخدم رأسًا مختلفًا لتغطية كل ضلع تم النظر فيه خلال العملية (لأنها تُشكل تطابقًا )، فإن تغطية الرؤوس الناتجة تكون على الأكثر ضعف التغطية المثلى. بعبارة أخرى، هذه خوارزمية تقريب ذات عامل ثابت يساوي 2. وفقًا لتخمين الألعاب الفريدة الأخير ، يُعد هذا العامل هو الأفضل على الإطلاق. [ 5 ]

تختلف مسائل NP-hard اختلافًا كبيرًا في قابليتها للتقريب؛ فبعضها، مثل مسألة حقيبة الظهر ، يمكن تقريبه ضمن عامل ضربي.1+ϵ{\displaystyle 1+\epsilon }، لأي ثابتϵ>0{\displaystyle \epsilon >0}وبالتالي، تُنتج هذه الخوارزميات حلولًا قريبة جدًا من الحل الأمثل (وتُسمى هذه المجموعة من خوارزميات التقريب مخطط تقريب زمني متعدد الحدود أو PTAS). بينما يستحيل تقريب بعضها الآخر ضمن أي عامل ثابت، أو حتى متعدد الحدود، إلا إذا كانت P = NP ، كما هو الحال في مسألة الزمرة القصوى . لذلك، تتمثل إحدى الفوائد المهمة لدراسة خوارزميات التقريب في تصنيف دقيق لصعوبة مختلف المسائل الصعبة من فئة NP، بما يتجاوز التصنيف الذي توفره نظرية اكتمال NP . بعبارة أخرى، على الرغم من أن مسائل NP الكاملة قد تكون متكافئة (في ظل اختزالات زمنية متعددة الحدود) من منظور الحلول الدقيقة، فإن مسائل التحسين المقابلة لها تتصرف بشكل مختلف تمامًا من منظور الحلول التقريبية.

تقنيات تصميم الخوارزميات

توجد الآن عدة تقنيات راسخة لتصميم خوارزميات التقريب. وتشمل هذه التقنيات ما يلي.

  1. خوارزمية جشعة
  2. البحث المحلي
  3. التعداد والبرمجة الديناميكية (والتي تُستخدم أيضًا في كثير من الأحيان للتقريبات ذات المعلمات )
  4. تقنيات البرمجة الرياضية. يتضمن ذلك نمذجة المشكلة المدروسة باستخدام صياغة برمجة رياضية مناسبة (عادةً ما تكون برمجة محدبة ) مثل البرمجة الخطية ، والبرمجة شبه المحددة ، وما إلى ذلك، للحصول على حلول مُبسّطة للمشكلة. ثم تُطبّق تقنيات خوارزمية إضافية على هذه الصياغات.
    • الطرق القائمة على التقريب. تتضمن هذه الطرق حل الصيغة المدروسة للحصول على حل كسري جيد، ثم تحويله إلى حل صحيح. تشمل تقنيات التقريب الشائعة التقريب البسيط بالعتبة، والتقريب العشوائي ، والتقريب التكراري ، وغيرها.
    • أساليب التوفيق الثنائي. يتضمن ذلك تفسير خوارزمية قائمة على التوافق (عادةً ما تكون خوارزمية جشعة) على أنها عملية حساب حل ممكن للبرنامج الثنائي للصيغة المدروسة.
    • الأساليب الأولية-الثنائية.
  5. تضمين المشكلة في مقياس معين ثم حل المشكلة بناءً على هذا المقياس. يُعرف هذا أيضاً باسم تضمين المقياس.
  6. أخذ العينات العشوائية واستخدام العشوائية بشكل عام بالتزامن مع الطرق المذكورة أعلاه.

الضمانات اللاحقة

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

صعوبة التقريب

ترتبط خوارزميات التقريب، كمجال بحثي، ارتباطًا وثيقًا بنظرية عدم التقريب، وتستند إليها ، حيث يُثبت عدم وجود خوارزميات فعّالة بنسب تقريب معينة (بناءً على فرضيات شائعة مثل فرضية P ≠ NP) عن طريق الاختزالات . في حالة مسألة البائع المتجول المتري، تستبعد أفضل نتيجة معروفة لعدم التقريب الخوارزميات ذات نسبة تقريب أقل من 123/122 ≈ 1.008196 إلا إذا كانت P = NP، كما ذكر كاربينسكي ولامبيس وشميد [ 6 ] . وبالاقتران مع معرفة وجود خوارزمية كريستوفيدس للتقريب بنسبة 1.5، يُشير هذا إلى أن عتبة التقريب لمسألة البائع المتجول المتري (إن وُجدت) تقع في مكان ما بين 123/122 و1.5.

على الرغم من إثبات نتائج عدم التقريب منذ سبعينيات القرن الماضي، إلا أن هذه النتائج تم التوصل إليها بوسائل مخصصة، ولم يكن هناك فهم منهجي متاح آنذاك. ولم تُكتشف الأدوات الحديثة لإثبات نتائج عدم التقريب إلا بعد نتيجة فيج، وجولدواسير، ولوفاس، وسافرا، وسيجيدي عام 1990 حول عدم تقريب المجموعة المستقلة [ 7 ] ، ونظرية PCP الشهيرة [ 8 ]. فعلى سبيل المثال، تُظهر نظرية PCP أن خوارزميات جونسون للتقريب لعام 1974 لمسائل Max SAT ، وتغطية المجموعات ، والمجموعة المستقلة ، والتلوين ، تحقق جميعها نسبة التقريب المثلى، بافتراض أن P ≠ NP [ 9 ] .

الجدوى العملية

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

في حالات أخرى، حتى لو كانت النتائج الأولية ذات أهمية نظرية بحتة، فإنه بمرور الوقت، ومع تحسن الفهم، يمكن تحسين الخوارزميات لتصبح أكثر عملية. ومن الأمثلة على ذلك خوارزمية PTAS الأولية لمسألة البائع المتجول الإقليدية التي وضعها سانجيف أرورا (وبشكل مستقل وضعها جوزيف ميتشل ) والتي كان وقت تشغيلها باهظًا للغاية.نيا(1/ϵ){\displaystyle n^{O(1/\epsilon )}}لـ1+ϵ{\displaystyle 1+\epsilon }[ 10 ] ومع ذلك، في غضون عام، تم دمج هذه الأفكار في وقت شبه خطييا(نسجل⁡ن){\displaystyle O(n\log n)}خوارزمية لأي ثابتϵ>0{\displaystyle \epsilon >0}[ 11 ]​

بنية خوارزميات التقريب

بالنظر إلى مسألة التحسين التالية:

Π:أنا×S{\displaystyle \Pi :I\times S}

أينΠ{\displaystyle \Pi }هي مسألة تقريبية،أنا{\displaystyle I}مجموعة المدخلات وS{\displaystyle S}من خلال مجموعة الحلول، يمكننا تعريف دالة التكلفة:

ج:S→R+{\displaystyle c:S\rightarrow \mathbb {R} ^{+}}

ومجموعة الحلول الممكنة:

∀أنا∈أنا،S(أنا)=s∈S:أناΠs{\displaystyle \forall i\in I,S(i)={s\in S:i\Pi _{s}}}

إيجاد الحل الأمثلs*{\displaystyle s^{*}}لمسألة تعظيم أو تصغير:

s*∈S(أنا){\displaystyle s^{*}\in S(i)}،ج(s*)=مأنان/مأx ج(S(أنا)){\displaystyle c(s^{*})=min/max\ c(S(i))}

بافتراض وجود حل ممكنs∈S(أنا){\displaystyle s\in S(i)}، معs≠s*{\displaystyle s\neq s^{*}}، نريد ضمانًا لجودة الحل، وهو أداء يجب ضمانه (عامل التقريب).

على وجه التحديد، امتلاكأΠ(أنا)∈Sأنا{\displaystyle A_{\Pi }(i)\in S_{i}}، تمتلك الخوارزمية عامل تقريب (أو نسبة تقريب ) منρ(ن){\displaystyle \rho (n)}لو∀أنا∈أنا s.ت.|أنا|=ن{\displaystyle \forall i\in I\ st|i|=n}لدينا:

  • لمسألة التصغير :ج(أΠ(أنا))ج(s*(أنا))≤ρ(ن){\displaystyle {\frac {c(A_{\Pi }(i))}{c(s^{*}(i))}}\leq \rho (n)}وهذا يعني بدوره أن الحل الذي اختارته الخوارزمية مقسومًا على الحل الأمثل يحقق نسبة قدرهاρ(ن){\displaystyle \rho (n)}؛
  • لمسألة تعظيم القيمة :ج(s*(أنا))ج(أΠ(أنا))≤ρ(ن){\displaystyle {\frac {c(s^{*}(i))}{c(A_{\Pi }(i))}}\leq \rho (n)}وهذا يعني بدوره أن نسبة الحل الأمثل مقسومًا على الحل الذي اختارته الخوارزمية تحقق نسبة قدرهاρ(ن){\displaystyle \rho (n)}؛

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

ضمانات الأداء

بالنسبة لبعض خوارزميات التقريب، من الممكن إثبات خصائص معينة تتعلق بتقريب النتيجة المثلى. على سبيل المثال، تُعرَّف خوارزمية التقريب ρ، A، بأنها خوارزمية ثبت فيها أن قيمة/تكلفة الحل التقريبي A ( x ) للحالة x ، f ( x )، لن تكون أكبر (أو أصغر، حسب الحالة) من عامل ρ مضروبًا في قيمة الحل الأمثل، OPT.

{ياPتي≤و(x)≤ρياPتي،لو ρ>1؛ρياPتي≤و(x)≤ياPتي،لو ρ<1.{\displaystyle {\begin{cases}\mathrm {OPT} \leq f(x)\leq \rho \mathrm {OPT} ,\qquad {\mbox{if }}\rho >1;\\\rho \mathrm {OPT} \leq f(x)\leq \mathrm {OPT} ,\qquad {\mbox{if }}\rho <1.\end{الحالات}}}

يُطلق على العامل ρ اسم ضمان الأداء النسبي . تتمتع خوارزمية التقريب بضمان أداء مطلق أو خطأ محدود c ، إذا ثبت لكل حالة x أن

(ياPتي-ج)≤و(x)≤(ياPتي+ج).{\displaystyle (\mathrm {OPT} -c)\leq f(x)\leq (\mathrm {OPT} +c).}

وبالمثل، يُعرَّف ضمان الأداء ، R ( x,y )، للحل y لحالة x على النحو التالي:

R(x،y)=الأعلى(ياPتيو(y)،و(y)ياPتي)،{\displaystyle R(x,y)=\max \left({\frac {OPT}{f(y)}},{\frac {f(y)}{OPT}}\right),}

حيث f ( y ) هي قيمة/تكلفة الحل y للحالة x . من الواضح أن ضمان الأداء أكبر من أو يساوي 1، ويساوي 1 إذا وفقط إذا كان y حلاً أمثل. إذا ضمنت خوارزمية A إرجاع حلول بضمان أداء لا يتجاوز r ( n )، يُقال إن A خوارزمية تقريبية من r ( n ) ولها نسبة تقريب r ( n ). وبالمثل، يُقال إن المسألة التي لها خوارزمية تقريبية من r(n) قابلة للتقريب من r ( n ) أو لها نسبة تقريب r ( n ) . [ 12 ] [ 13 ]

في مسائل التصغير، يقدم الضمانان المختلفان نفس النتيجة، أما في مسائل التعظيم، فإن ضمان الأداء النسبي ρ يعادل ضمان أداء ρر=ρ-1{\displaystyle r=\rho ^{-1}}في الأدبيات، كلا التعريفين شائعان ولكن من الواضح أي تعريف يتم استخدامه لأنه بالنسبة لمسائل التعظيم، فإن ρ ≤ 1 بينما r ≥ 1.

ضمان الأداء المطلقPأ{\displaystyle \mathrm {P} _{A}}لخوارزمية تقريبية A ، حيث يشير x إلى حالة من حالات المشكلة، وحيثRأ(x){\displaystyle R_{A}(x)}هل ضمان أداء A على x (أي ρ لحالة المشكلة x ) هو:

Pأ=معلومات{ر≥1|Rأ(x)≤ر،∀x}.{\displaystyle \mathrm {P} _{A}=\inf\{r\geq 1\mid R_{A}(x)\leq r,\forall x\}.}

أي أنPأ{\displaystyle \mathrm {P} _{A}}يمثل هذا الحد الأقصى لنسبة التقريب، r ، التي يمكن ملاحظتها في جميع الحالات الممكنة للمسألة. وبالمثل، فإن نسبة الأداء التقاربيRأ∞{\displaystyle R_{A}^{\infty }}يكون:

Rأ∞=معلومات{ر≥1|∃ن∈Z+،Rأ(x)≤ر،∀x،|x|≥ن}.{\displaystyle R_{A}^{\infty }=\inf\{r\geq 1\mid \exists n\in \mathbb {Z} ^{+},R_{A}(x)\leq r,\forall x,|x|\geq n\}.}

بمعنى آخر، هو نفسه نسبة الأداء المطلقة ، مع حد أدنى n لحجم حالات المشكلة. يُستخدم هذان النوعان من النسب لوجود خوارزميات يكون فيها الفرق بينهما كبيرًا.

ضمانات الأداء
r -approx [ 12 ] [ 13 ]ρ -تقريبًاخطأ نسبي [ 13 ]خطأ نسبي [ 12 ]الخطأ النسبي المعياري [ 12 ] [ 13 ]خطأ مطلق [ 12 ] [ 13 ]
الأعلى:و(x)≥{\displaystyle f(x)\geq }ر-1ياPتي{\displaystyle r^{-1}\mathrm {OPT} }ρياPتي{\displaystyle \rho \mathrm {OPT} }(1-ج)ياPتي{\displaystyle (1-c)\mathrm {OPT} }(1-ج)ياPتي{\displaystyle (1-c)\mathrm {OPT} }(1-ج)ياPتي+جدبليوياRSتي{\displaystyle (1-c)\mathrm {OPT} +c\mathrm {WORST} }ياPتي-ج{\displaystyle \mathrm {OPT} -c}
دقيقة:و(x)≤{\displaystyle f(x)\leq }رياPتي{\displaystyle r\mathrm {OPT} }ρياPتي{\displaystyle \rho \mathrm {OPT} }(1+ج)ياPتي{\displaystyle (1+c)\mathrm {OPT} }(1-ج)-1ياPتي{\displaystyle (1-c)^{-1}\mathrm {OPT} }(1-ج)-1ياPتي+جدبليوياRSتي{\displaystyle (1-c)^{-1}\mathrm {OPT} +c\mathrm {WORST} }ياPتي+ج{\displaystyle \mathrm {OPT} +c}

مصطلحات إبسيلون

في الأدبيات، تعني نسبة التقريب لمسألة تعظيم (تصغير) c - ϵ (min: c + ϵ) أن الخوارزمية لها نسبة تقريب c ∓ ϵ لأي قيمة ϵ > 0، ولكن لم يتم (أو لا يمكن) إثبات هذه النسبة لـ ϵ = 0. ومن الأمثلة على ذلك نسبة عدم التقريب الأمثل - أي عدم وجود تقريب - وهي 7 / 8 + ϵ لحالات MAX-3SAT القابلة للإرضاء ، والتي وضعها يوهان هاستاد . [ 14 ] وكما ذُكر سابقًا، عندما c = 1، يُقال إن المسألة لها مخطط تقريب زمني متعدد الحدود .

قد يظهر حدّ ϵ عندما تُدخل خوارزمية تقريبية خطأً ضربيًا وخطأً ثابتًا، بينما يؤول الحد الأدنى الأمثل للحالات ذات الحجم n إلى اللانهاية مع ازدياد n . في هذه الحالة، تكون نسبة التقريب c ∓ k / OPT = c ∓ o(1) لبعض الثوابت c و k . بفرض قيمة ϵ > 0 عشوائية، يمكن اختيار N كبيرة بما يكفي بحيث يكون الحد k / OPT < ϵ لكل n ≥ N. لكل قيمة ثابتة لـ ϵ، يمكن حلّ الحالات ذات الحجم n < N باستخدام البحث الشامل، مما يُظهر نسبة تقريب - أي وجود خوارزميات تقريبية مضمونة - مقدارها c ∓ ϵ لكل ϵ > 0.

انظر أيضاً

الاقتباسات

  1. 1 2 برنارد، شمويز، ديفيد (2011). تصميم خوارزميات التقريب . مطبعة جامعة كامبريدج. ISBN 9780521195270. OCLC 671709856 . {{cite book}}: صيانة CS1: أسماء متعددة: قائمة المؤلفين ( رابط )
  2. ↑ لينسترا، جان كاريل؛ شمويس، ديفيد ب.؛ تاردوس، إيفا (1990-01-01). "خوارزميات تقريبية لجدولة الآلات المتوازية غير المرتبطة". البرمجة الرياضية . 46 ( 1-3 ): 259-271 . CiteSeerX 10.1.1.115.708 . doi : 10.1007/BF01585745 . ISSN 0025-5610 . S2CID 206799898 .   
  3. ↑ أغراوال، أجيت؛ كلاين، فيليب؛ رافي، ر. (1991). "عندما تصطدم الأشجار" . وقائع الندوة السنوية الثالثة والعشرين لجمعية ACM حول نظرية الحوسبة - STOC '91 . نيو أورليانز، لويزيانا، الولايات المتحدة: مطبعة ACM. الصفحات 134-144 . doi : 10.1145/103418.103437 . ISBN  978-0-89791-397-3. S2CID 1245448 . 
  4. ↑ غومانز، ميشيل إكس؛ ويليامسون، ديفيد ب. (نوفمبر 1995). "خوارزميات تقريب محسّنة لمسائل القطع الأقصى والإرضاء باستخدام البرمجة شبه المحددة". مجلة ACM . 42 (6): 1115-1145 . CiteSeerX 10.1.1.34.8500 . doi : 10.1145/227683.227684 . ISSN 0004-5411 . S2CID 15794408 .   
  5. ↑ خوت، سوبهاش؛ ريجيف، أوديد (2008-05-01). "قد يكون من الصعب تقريب تغطية الرؤوس في حدود 2−ε" . مجلة علوم الحاسوب والأنظمة . التعقيد الحسابي 2003. 74 (3): 335–349 . doi : 10.1016/j.jcss.2007.06.019 .
  6. ↑ كاربينسكي، ماريك؛ لامبيس، مايكل؛ شميد، ريتشارد (2015-12-01). "حدود جديدة لعدم التقريب لمسألة البائع المتجول". مجلة علوم الحاسوب والأنظمة . 81 (8): 1665-1677 . arXiv : 1303.6437 . doi : 10.1016/j.jcss.2015.06.003 .
  7. ^ فيج، أوريل. غولدفاسر، شافعي؛ لوفاسز، لازلو؛ سفرا، شموئيل؛ سيجيدي ، ماريو (مارس 1996). "البراهين التفاعلية وصلابة تقريب الزمر" . جي ايه سي ام . 43 (2): 268-292 . دوى : 10.1145 / 226643.226652 . ISSN 0004-5411 . 
  8. ↑ أرورا، سانجيف؛ صفرا، شموئيل (يناير 1998). "التحقق الاحتمالي من البراهين: توصيف جديد لـ NP" . مجلة ACM . 45 (1): 70-122 . doi : 10.1145/273865.273901 . ISSN 0004-5411 . S2CID 751563 .  
  9. ↑ جونسون، ديفيد س. (1974-12-01). "خوارزميات التقريب للمسائل التوافقية" . مجلة علوم الحاسوب والنظم . 9 (3): 256-278 . doi : 10.1016/S0022-0000(74)80044-9 .
  10. ↑ أرورا، س. (أكتوبر 1996). "مخططات تقريبية متعددة الحدود لمسألة البائع المتجول الإقليدية وغيرها من المسائل الهندسية". وقائع المؤتمر السابع والثلاثين حول أسس علوم الحاسوب . ص 2-11. CiteSeerX 10.1.1.32.3376 . doi : 10.1109 / SFCS.1996.548458 . ISBN   978-0-8186-7594-2. S2CID 1499391 . 
  11. ↑ أرورا، س. (أكتوبر 1997). "مخططات تقريبية شبه خطية لمسألة البائع المتجول الإقليدية وغيرها من المسائل الهندسية". وقائع الندوة السنوية الثامنة والثلاثين حول أسس علوم الحاسوب . الصفحات 554-563 . doi : 10.1109/SFCS.1997.646145 . ISBN  978-0-8186-8197-4. S2CID 10656723 . 
  12. 1 2 3 4 5 جي. أوسييلو؛ بي. كريشينزي؛ جي. جامبوسي؛ في. كان؛ أ. ماركيتي-سباكاميلا؛ إم. بروتاسي (1999). التعقيد والتقريب: مسائل التحسين التوافقي وخصائص قابلية التقريب الخاصة بها .
  13. 1 2 3 4 5 فيجو كان (1992). حول إمكانية تقريب مسائل التحسين الكاملة من نوع NP (PDF) .
  14. ↑ يوهان هاستاد (1999). "بعض نتائج عدم التقريب الأمثل" . مجلة ACM . 48 (4): 798-859 . CiteSeerX 10.1.1.638.2808 . doi : 10.1145/502090.502098 . S2CID 5120748 .  

مراجع