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

في علوم الكمبيوتر وبحوث العمليات، تعد خوارزميات التقريب خوارزميات فعالة تعمل على إيجاد حلول تقريبية لمشاكل التحسين (وخاصة مشاكل مسائل NP صعبة) مع ضمانات قابلة للإثبات على مسافة الحل المرتجع إلى الحل الأمثل.^[1] تنشأ خوارزميات التقريب بشكل طبيعي في مجال علوم الكمبيوتر النظرية كنتيجة لتخمين P ≠ NP المعتقد على نطاق واسع. بموجب هذا التخمين، لا يمكن حل فئة واسعة من مشاكل التحسين بدقة في وقت متعدد الحدود. لذلك، يحاول مجال خوارزميات التقريب فهم مدى إمكانية تقريب الحلول المثلى لمثل هذه المشاكل في وقت متعدد الحدود. في الغالبية العظمى من الحالات، فإن ضمان مثل هذه الخوارزميات هو ضمان مضاعف يتم التعبير عنه بنسبة تقريب أو عامل تقريب، أي أن الحل الأمثل مضمون دائمًا ليكون ضمن عامل مضاعف (محدد مسبقًا) للحل المرتجع. ومع ذلك، هناك أيضًا العديد من خوارزميات التقريب التي توفر ضمانًا إضافيًا لجودة الحل المرتجع. من الأمثلة البارزة لخوارزمية التقريب التي توفر كلاً من الخوارزمية الكلاسيكية للنسترا وشمويس وتاردوس^[2] للجدولة على الآلات المتوازية غير ذات الصلة.

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

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

مقدمة

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

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

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

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

خوارزمية الجشع
البحث المحلي
الترقيم والبرمجة الديناميكية (والتي تُستخدم أيضًا في كثير من الأحيان للتقريبات المعلمة ^{[لغات أخرى]}‏)
حل استرخاء البرمجة المحدب للحصول على حل كسري. ثم تحويل هذا الحل الكسري إلى حل قابل للتطبيق من خلال التقريب المناسب. تتضمن الاسترخاءات الشعبية ما يلي:
- استرخاءات البرمجة الخطية
- استرخاءات البرمجة شبه المحددة ^{[لغات أخرى]}‏
الطرق الثنائية البدائية
تركيب مزدوج
تضمين المشكلة في بعض المقاييس ثم حل المشكلة بناءً على هذا المقياس. يُعرف هذا أيضًا بالتضمين المتري.
- العينة العشوائية واستخدام العشوائية بشكل عام بالتزامن مع الأساليب المذكورة أعلاه.

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

في حين أن خوارزميات التقريب توفر دائمًا ضمانًا لأسوأ حالة مسبقًا (سواء كان إضافيًا أو مضاعفًا)، فإنها توفر في بعض الحالات أيضًا ضمانًا لاحقًا يكون في كثير من الأحيان أفضل بكثير. هذا هو الحال غالبًا بالنسبة للخوارزميات التي تعمل عن طريق حل استرخاء محدب لمشكلة التحسين على المدخلات المحددة. على سبيل المثال، هناك خوارزمية تقريب مختلفة لتغطية الرأس الأدنى والتي تحل استرخاء البرمجة الخطية ^{[لغات أخرى]}‏ للعثور على تغطية رأس تكون على الأكثر ضعف قيمة الاسترخاء. نظرًا لأن قيمة الاسترخاء لا تكون أكبر أبدًا من حجم غطاء الرأس الأمثل، فإن هذا يؤدي إلى خوارزمية تقريب أخرى ذات 2. في حين أن هذا مشابه للضمان المسبق لخوارزمية التقريب السابقة، فإن ضمان الأخيرة يمكن أن يكون أفضل بكثير (في الواقع عندما تكون قيمة استرخاء LP بعيدة عن حجم غطاء الرأس الأمثل).

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

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

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

العملية

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

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

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

نظرا لمشكلة التحسين:

$\Pi :I\times S$

أين $\Pi$ هي مشكلة تقريبية، $I$ مجموعة المدخلات و $S$ مجموعة الحلول، يمكننا تعريف دالة التكلفة:

$c:S\rightarrow \mathbb {R} ^{+}$

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

$\forall i\in I,S(i)={s\in S:i\Pi _{s}}$

إيجاد الحل الأفضل $s^{*}$ لمشكلة التعظيم أو التصغير:

$s^{*}\in S(i)$ , $c(s^{*})=min/max\ c(S(i))$

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

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

لمشكلة التقليل : ${\frac {c(A_{\Pi }(i))}{c(s^{*}(i))}}\leq \rho (n)$ ، وهو ما يعني بدوره أن الحل الذي اتخذته الخوارزمية مقسومًا على الحل الأمثل يحقق نسبة $\rho (n)$ ؛
لمشكلة التعظيم : ${\frac {c(s^{*}(i))}{c(A_{\Pi }(i))}}\leq \rho (n)$ ، وهو ما يعني بدوره أن الحل الأمثل مقسومًا على الحل الذي اتخذته الخوارزمية يحقق نسبة $\rho (n)$ ؛

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

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

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

{\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{cases}}

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

(\mathrm {OPT} -c)\leq f(x)\leq (\mathrm {OPT} +c).

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

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]

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

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

\mathrm {P} _{A}=\inf\{r\geq 1\mid R_{A}(x)\leq r,\forall x\}.

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

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-أبروكس^[12]^[13]	ρ-أبروكس	خطأ نسبي^[13]	خطأ نسبي^[12]	خطأ معياري نسبي^[12]^[13]	خطأ في القيمة المطلقة^[12]^[13]
الأعلى: $f(x)\geq$	$r^{-1}\mathrm {OPT}$	$\rho \mathrm {OPT}$	$(1-c)\mathrm {OPT}$	$(1-c)\mathrm {OPT}$	$(1-c)\mathrm {OPT} +c\mathrm {WORST}$	$\mathrm {OPT} -c$
الأدنى: $f(x)\leq$	$r\mathrm {OPT}$	$\rho \mathrm {OPT}$	$(1+c)\mathrm {OPT}$	$(1-c)^{-1}\mathrm {OPT}$	$(1-c)^{-1}\mathrm {OPT} +c\mathrm {WORST}$	$\mathrm {OPT} +c$

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

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

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

الاستشهادات

^ ^ا ^ب Bernard.، Shmoys, David (2011). The design of approximation algorithms. Cambridge University Press. ISBN:9780521195270. OCLC:671709856. مؤرشف من الأصل في 2025-04-23.{{استشهاد بكتاب}}: صيانة الاستشهاد: أسماء متعددة: قائمة المؤلفين (link)
^ Lenstra, Jan Karel; Shmoys, David B.; Tardos, Éva (1 Jan 1990). "Approximation algorithms for scheduling unrelated parallel machines". Mathematical Programming (بالإنجليزية). 46 (1–3): 259–271. CiteSeerX:10.1.1.115.708. DOI:10.1007/BF01585745. ISSN:0025-5610. S2CID:206799898.
^ Agrawal, Ajit; Klein, Philip; Ravi, R. (1991). "When trees collide". Proceedings of the twenty-third annual ACM symposium on Theory of computing - STOC '91 (بالإنجليزية). New Orleans, Louisiana, United States: ACM Press. pp. 134–144. DOI:10.1145/103418.103437. ISBN:978-0-89791-397-3. S2CID:1245448.
^ Goemans، Michel X.؛ Williamson، David P. (نوفمبر 1995). "Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming". J. ACM. ج. 42 ع. 6: 1115–1145. CiteSeerX:10.1.1.34.8500. DOI:10.1145/227683.227684. ISSN:0004-5411. S2CID:15794408.
^ Khot، Subhash؛ Regev، Oded (1 مايو 2008). "Vertex cover might be hard to approximate to within 2−ε". Journal of Computer and System Sciences. Computational Complexity 2003. ج. 74 ع. 3: 335–349. DOI:10.1016/j.jcss.2007.06.019.
^ Karpinski، Marek؛ Lampis، Michael؛ Schmied، Richard (1 ديسمبر 2015). "New inapproximability bounds for TSP". Journal of Computer and System Sciences. ج. 81 ع. 8: 1665–1677. arXiv:1303.6437. DOI:10.1016/j.jcss.2015.06.003.
^ Feige، Uriel؛ Goldwasser، Shafi؛ Lovász، Laszlo؛ Safra، Shmuel؛ Szegedy، Mario (مارس 1996). "Interactive Proofs and the Hardness of Approximating Cliques". J. ACM. ج. 43 ع. 2: 268–292. DOI:10.1145/226643.226652. ISSN:0004-5411.
^ Arora، Sanjeev؛ Safra، Shmuel (يناير 1998). "Probabilistic Checking of Proofs: A New Characterization of NP". J. ACM. ج. 45 ع. 1: 70–122. DOI:10.1145/273865.273901. ISSN:0004-5411. S2CID:751563.
^ Johnson، David S. (1 ديسمبر 1974). "Approximation algorithms for combinatorial problems". Journal of Computer and System Sciences. ج. 9 ع. 3: 256–278. DOI:10.1016/S0022-0000(74)80044-9.
^ Arora، S. (أكتوبر 1996). "Polynomial time approximation schemes for Euclidean TSP and other geometric problems". Proceedings of 37th Conference on Foundations of Computer Science. ص. 2–11. CiteSeerX:10.1.1.32.3376. DOI:10.1109/SFCS.1996.548458. ISBN:978-0-8186-7594-2. S2CID:1499391.
^ Arora، S. (أكتوبر 1997). "Nearly linear time approximation schemes for Euclidean TSP and other geometric problems". Proceedings 38th Annual Symposium on Foundations of Computer Science. ص. 554–563. DOI:10.1109/SFCS.1997.646145. ISBN:978-0-8186-8197-4. S2CID:10656723.
^ ^ا ^ب ^ج ^د ^ه G. Ausiello؛ P. Crescenzi؛ G. Gambosi؛ V. Kann؛ A. Marchetti-Spaccamela؛ M. Protasi (1999). Complexity and Approximation: Combinatorial Optimization Problems and their Approximability Properties.
^ ^ا ^ب ^ج ^د ^ه Viggo Kann (1992). On the Approximability of NP-complete Optimization Problems (PDF). مؤرشف من الأصل (PDF) في 2025-03-08.
^ Johan Håstad (1999). "Some Optimal Inapproximability Results". Journal of the ACM. ج. 48 ع. 4: 798–859. CiteSeerX:10.1.1.638.2808. DOI:10.1145/502090.502098. S2CID:5120748. مؤرشف من الأصل في 2024-04-21.

المراجع

Vazirani، Vijay V. (2003). Approximation Algorithms. Berlin: Springer. ISBN:978-3-540-65367-7.
Thomas H. Cormen، Charles E. Leiserson، Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. (ردمك 0-262-03293-7)ISBN 0-262-03293-7. Chapter 35: Approximation Algorithms, pp. 1022–1056.
Dorit S. Hochbaum, ed. Approximation Algorithms for NP-Hard problems, PWS Publishing Company, 1997. (ردمك 0-534-94968-1)ISBN 0-534-94968-1. Chapter 9: Various Notions of Approximations: Good, Better, Best, and More
Williamson، David P.؛ Shmoys، David B. (26 أبريل 2011)، The Design of Approximation Algorithms، مطبعة جامعة كامبريدج، ISBN:978-0521195270

وصلات خارجية

بييرلويجي كريسينزي، فيجو كان، ماجنوس هالدورسون، ماريك كاربينسكي ^{[لغات أخرى]}‏ وجيرهارد ووجينجر ^{[لغات أخرى]}‏، خلاصة وافية لمشاكل تحسين NP.

[Bernard._2011-1] ا ^ب Bernard.، Shmoys, David (2011). The design of approximation algorithms. Cambridge University Press. ISBN:9780521195270. OCLC:671709856. مؤرشف من الأصل في 2025-04-23.{{استشهاد بكتاب}}: صيانة الاستشهاد: أسماء متعددة: قائمة المؤلفين (link)

[2] Lenstra, Jan Karel; Shmoys, David B.; Tardos, Éva (1 Jan 1990). "Approximation algorithms for scheduling unrelated parallel machines". Mathematical Programming (بالإنجليزية). 46 (1–3): 259–271. CiteSeerX:10.1.1.115.708. DOI:10.1007/BF01585745. ISSN:0025-5610. S2CID:206799898.

[3] Agrawal, Ajit; Klein, Philip; Ravi, R. (1991). "When trees collide". Proceedings of the twenty-third annual ACM symposium on Theory of computing - STOC '91 (بالإنجليزية). New Orleans, Louisiana, United States: ACM Press. pp. 134–144. DOI:10.1145/103418.103437. ISBN:978-0-89791-397-3. S2CID:1245448.

[4] Goemans، Michel X.؛ Williamson، David P. (نوفمبر 1995). "Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming". J. ACM. ج. 42 ع. 6: 1115–1145. CiteSeerX:10.1.1.34.8500. DOI:10.1145/227683.227684. ISSN:0004-5411. S2CID:15794408.

[5] Khot، Subhash؛ Regev، Oded (1 مايو 2008). "Vertex cover might be hard to approximate to within 2−ε". Journal of Computer and System Sciences. Computational Complexity 2003. ج. 74 ع. 3: 335–349. DOI:10.1016/j.jcss.2007.06.019.

[6] Karpinski، Marek؛ Lampis، Michael؛ Schmied، Richard (1 ديسمبر 2015). "New inapproximability bounds for TSP". Journal of Computer and System Sciences. ج. 81 ع. 8: 1665–1677. arXiv:1303.6437. DOI:10.1016/j.jcss.2015.06.003.

[7] Feige، Uriel؛ Goldwasser، Shafi؛ Lovász، Laszlo؛ Safra، Shmuel؛ Szegedy، Mario (مارس 1996). "Interactive Proofs and the Hardness of Approximating Cliques". J. ACM. ج. 43 ع. 2: 268–292. DOI:10.1145/226643.226652. ISSN:0004-5411.

[8] Arora، Sanjeev؛ Safra، Shmuel (يناير 1998). "Probabilistic Checking of Proofs: A New Characterization of NP". J. ACM. ج. 45 ع. 1: 70–122. DOI:10.1145/273865.273901. ISSN:0004-5411. S2CID:751563.

[9] Johnson، David S. (1 ديسمبر 1974). "Approximation algorithms for combinatorial problems". Journal of Computer and System Sciences. ج. 9 ع. 3: 256–278. DOI:10.1016/S0022-0000(74)80044-9.

[10] Arora، S. (أكتوبر 1996). "Polynomial time approximation schemes for Euclidean TSP and other geometric problems". Proceedings of 37th Conference on Foundations of Computer Science. ص. 2–11. CiteSeerX:10.1.1.32.3376. DOI:10.1109/SFCS.1996.548458. ISBN:978-0-8186-7594-2. S2CID:1499391.

[11] Arora، S. (أكتوبر 1997). "Nearly linear time approximation schemes for Euclidean TSP and other geometric problems". Proceedings 38th Annual Symposium on Foundations of Computer Science. ص. 554–563. DOI:10.1109/SFCS.1997.646145. ISBN:978-0-8186-8197-4. S2CID:10656723.

[ausiello99complexity-12] ا ^ب ^ج ^د ^ه G. Ausiello؛ P. Crescenzi؛ G. Gambosi؛ V. Kann؛ A. Marchetti-Spaccamela؛ M. Protasi (1999). Complexity and Approximation: Combinatorial Optimization Problems and their Approximability Properties.

[kann92onthe-13] ا ^ب ^ج ^د ^ه Viggo Kann (1992). On the Approximability of NP-complete Optimization Problems (PDF). مؤرشف من الأصل (PDF) في 2025-03-08.

[hastad99someoptimal-14] Johan Håstad (1999). "Some Optimal Inapproximability Results". Journal of the ACM. ج. 48 ع. 4: 798–859. CiteSeerX:10.1.1.638.2808. DOI:10.1145/502090.502098. S2CID:5120748. مؤرشف من الأصل في 2024-04-21.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]