الگوریتم‌های تقریبی
اهداف درس
بسیاری از مسائل بهینه‌سازی در ریاضیات، علوم کامپیوتر، و مهندسی ان‌پی-سخت هستند و بنابراین به دست آوردن جواب‌های بهینه برای این مسائل در زمان چندجمله‌ای نامحتمل است. الگوریتم‌های تقریبی این امکان را فراهم می‌آورند که جواب‌هایی نزدیک به جواب بهینه با ضریب تقریب قابل اثبات برای این دسته از مسائل به دست آورد. هدف اين درس، آشنایی با مفاهیم و تکنیک‌های متداول در طراحی الگوریتم‌های تقریبی حول محور مسائل بنیادی در بهینه‌سازی ترکیبیاتی، و نیز بررسی روش‌های اثبات سختی تقریب برخی از این مسائل است.
ريز مواد
- مقدمات
- مسائل ان‌پی-بهینه‌سازی
- الگوریتم‌های تقریبی
- درجه‌ی تقریب‌پذیری
- روش‌های ترکیبیاتی
- الگوریتم‌های حریصانه
- جست‌وجوی محلی
- تکنیک لایه‌بندی
- هرس پارامتری
- برنامه‌ریزی پویا
- گرد کردن
- روش‌های توری
- روش‌های مبتنی بر برنامه‌ریزی خطی
- گردکردن قطعی (deterministic rounding)
- گردکردن تصادفی (randomized rounding)
- روش بیضوی (ellipsoid method)
- برازش دوگان (dual-fitting)
- روش اولیه-دوگان (primal-dual method)
- برنامه‌ریزی نیمه‌معین (semidefinite programming)
- برنامه‌ریزی برداری (vector programming)
- مسائل بهینه‌سازی
- مسائل پوششی: پوشش رأسی، پوشش مجموعه‌ای
- مسائل شبکه‌ای: درخت‌های اشتاینر، درخت اشتاینر جمع‌کننده‌ی جایزه
- مسائل گشت: فروشنده‌ی دوره‌گرد، فروشنده‌ی دوره‌گرد اقلیدسی
- مسائل برش: برش بیشینه، برش چندگانه
- مسائل عددی: کوله‌پشتی، بسته‌بندی
- مسائل هندسی: قطر نقاط، مجموعه‌ی مستقل در مربع‌های واحد
- مسائل صدق‌پذیری: k-صدق‌پذیری بیشینه
- مسائل خوشه‌بندی: k-مرکز، مکان‌یابی تسهیلات
- مسائل زمان‌بندی: زمان‌بندی کارها با پردازنده‌‌های موازی
- سختی تقریب
- اثبات‌های اولیه
- کاهش با ایجاد فاصله
- کاهش با حفظ درجه‌ی تقریب
ارزیابی
- آزمون‌های میان‌ترم و پایان‌ترم (۱۰ نمره)
- سه تمرین نظری (۶ نمره)
- پروژه‌ی پژوهشی (۴ نمره)
مراجع
- V. Vazirani. Approximation Algorithms. Springer-Verlag, 2001.
- D. Williamson and D. Shmoys. The Design of Approximation Algorithms. Cambridge University Press, 2011.