مروری بر آنچه گذشت.. (الگوریتم تقریبی)

وزیرانی:

۱- مقدمه: پوشش رأسی، کران پایین برای جواب بهینه، تطابق بیشینه، دوگان LP و قضیه مینیمم-ماکسیمم، تبدیل مسأله‌های دیگر به پوشش رأسی

۲- الگوریتم‌های ترکیبیاتی-پوشش مجموعه‌ای: الگوریتم حریصانه، کران تطبیق‌پذیر و ضریب تقریب H(n)، مثال tight برای ضریب تقریب، تکنیک لایه‌ای: حل مسأله‌های دیگر با پوشش مجموعه‌ای، بهبود ضریب تقریب با پیدا کردن کران بهتر (تطبیق پذیر)، هرس فضای نمونه و پیشامد برای بهبود ضریب تقریب (تطبیق پذیر)

۳- الگوریتم‌های ترکیبیاتی-فروشنده دوره‌گرد و درخت اشتاینر: تبدیل یک مساله به مساله دیگر با حفظ ضریب تقریب، متریک کوتاهترین مسیر و بستار متریک، تقریب ناپذیری، جایگزین کردن دو یال با یک یال در گراف کامل متریک، ترکیب دو راه حل مسأله برای رسیدن به ضریب تقریب بهتر

۴- الگوریتم‌های ترکیبیاتی- چندبرش و k-برش، تبدیل مسأله خواستار هزینه مینیمم و مسأله خواستار اعضای بهینه، تغییر هزینه با حذف و اضافه کردن عضو (تطبیق پذیر)، مثال tight دارای اپسیلون، درخت گومری-هو، خلاصه کردن مسأله با حفظ هزینه

۵- الگوریتم‌های ترکیبیاتی-k-مرکز: هرس پارامتری،‌ توانی از گراف (ماتریس مجاورت)

*۶- پوشش رأسی با فیدبک: جمعی بودن هزینه، مدل کردن با رشته دودویی، تکنیک لایه‌ای برای هزینه جمعی، حالت‌بندی و انتخاب بهینه برای قسمتی از مسأله

*۷- کوتاهترین ابررشته: پیدا کردن کران برای مجموع خطا در محاسبه ضریب تقریب، تبدیل به مسأله‌ی با ضریب تقریب بهتر با تغییر هزینه، تقریب قسمت‌های مختلف مسأله

۸- کوله‌پشتی: شمای تقریبی، الگوریتم شبه چندجمله‌ای، رندکردن بیتی، برنامه نویسی پویا برای به دست آوردن جواب بهینه مسأله رند شده، وجود شمای تقریبی چندجمله‌ای کامل و np-سخت بودن قوی، رند کردن برای رسیدن به مقدار لازم برای رسیدن به تقریب داده شده

۹- سطل‌بندی: شمای تقریبی مجانبی، حل مسأله برای جوابهای بهینه کوچک و رند کردن مسأله‌های بزرگ به کوچک، استفاده از الگوریتم‌های تقریبی برای حالت‌های کوچک

*۱۰- کوتاهترین برنامه: کران پائین دوتایی (ترکیبی)، هزینه پارامتری و جستجوی دودویی برای به دست آوردن پارامتر بهینه، ثابت فرض کردن یک پارامتر، شمای تقریبی چندجمله‌ای

*۱۱- فروشنده دوره‌گرد اقلیدسی: به دست آوردن جواب دانه درشت به صورت تصادفی، جعبه محیطی، تقسیم صفحه با شیفت دادن تصادفی مجموعه خطوط، درخت چهارتایی، توری سلسله مراتبی

۱۲- الگوریتم‌های بر مبنای LP-دوگان LP، قضیه دوگان ضعیف، شرایط بهینه بودن جواب، روابط مینیمم و ماکسیمم، integer programming، رند کردن LP، شمای اولیه-ثانویه، روش dual fitting، فاصله صحیح بودن یک تبدیل LP (نسبت صحیح بودن)، پیشگوی جداکننده