الگوریتم‌های تقریبی

Approximation Algorithms

شماره درس: ۴۰۸۳۴	تعداد واحد: ۳
مقطع: کارشناسی ارشد	نوع درس: نظری
پیش‌نیاز: –	هم‌نیاز: –

اهداف درس

بسیاری از مسائل بهینه‌سازی در ریاضیات، علوم کامپیوتر و مهندسی ان‌پی-سخت هستند و بنابراین به دست‌ آوردن جواب‌های بهینه برای این دسته از مسائل در زمان چندجمله‌ای با فرض P ≠ NP امکان‌پذیر نیست. الگوریتم‌های تقریبی امکان دست‌یابی به جواب‌هایی نزدیک به جواب‌ بهینه با ضریب تقریب قابل اثبات را برای این دسته از مسائل فراهم می‌آورند. هدف از این درس، آشنایی با مفاهیم و تکنیک‌های متداول در طراحی الگوریتم‌های تقریبی حول محور مسائل بنیادی در بهینه‌سازی ترکیبیاتی، و نیز آشنایی با روش‌های اثبات سختی تقریب برای برخی از این مسائل است.

ریز مواد

مقدمات (۲ جلسه)
- مسائل ان‌پی-بهینه‌سازی
- الگوریتم‌های تقریبی
- درجه‌ی تقریب‌پذیری
روش‌های ترکیبیاتی (۶ جلسه)
- الگوریتم‌های حریصانه
- جست‌وجوی محلی
- تکنیک لایه‌بندی
- هرس پارامتری
- برنامه‌ریزی پویا
- گرد کردن
- روش‌های توری
روش‌های مبتنی بر برنامه‌ریزی خطی (۸ جلسه)
- گردکردن قطعی
- گردکردن تصادفی
- روش بیضوی
- روش اولیه-دوگان
- روش برازش دوگان
- برنامه‌ریزی نیمه‌معین
- برنامه‌ریزی برداری
مسائل بهینه‌سازی (۸ جلسه)
- مسائل پوششی: پوشش رأسی، پوشش مجموعه‌ای
- مسائل شبکه‌ای: درخت‌های اشتاینر، درخت اشتاینر جمع‌کننده‌ی جایزه
- مسائل گشت: فروشنده‌ی دوره‌گرد، فروشنده‌ی دوره‌گرد اقلیدسی
- مسائل برش: برش بیشینه، k-برش، برش چندگانه
- مسائل عددی: کوله‌پشتی، بسته‌بندی
- مسائل هندسی: مجموعه‌ی مستقل در مربع‌های واحد
- مسائل صدق‌پذیری: k-صدق‌پذیری بیشینه
- مسائل خوشه‌بندی: k-مرکز، مکان‌یابی تسهیلات
- مسائل زمان‌بندی: زمان‌بندی کارها با پردازنده‌های موازی
سختی تقریب (۲ جلسه)
- اثبات‌های اولیه
- کاهش با ایجاد فاصله
- کاهش با حفظ درجه‌ی تقریب
- حدس بازی‌های یکتا
- قضیه‌ی PCP (در صورت فرصت)

ارزیابی

آزمون‌: آزمون‌های میان‌نیم‌سال و پایان‌نیم‌سال (۵۵ درصد نمره)
تمرین: دو یا سه تمرین نظری (۲۵ درصد نمره)
پروژه‌: پروژه‌ی پژوهشی (۲۰ درصد نمره)

مراجع

V. Vazirani. Approximation Algorithms. Springer-Verlag, 2001.
D. Williamson and D. Shmoys. The Design of Approximation Algorithms. Cambridge University Press, 2011.