Feedback vertex set

http://www.cs.cmu.edu/afs/cs/academic/class/15854-f05/www/scribe/lec9.pdf

http://www.sciencedirect.com/science/article/pii/S0022000008000500

تمرین تقریبی ۲

http://ce.sharif.edu/courses/92-93/2/ce726-1/assignments/files/assignDir17/exercise%202.pdf

مسأله الگوریتم تقریبی سال قبل

من داشتم حل تمرین‌های سال قبل را می‌نوشتم ولی انگار ذخیره نشده بود. سوال این بود که یک ماتریس ۰ و ۱ داریم می‌خواهیم ببینیم حالتی هست که ستون‌ها را جا به جا کنیم و همه‌ی ۱ ها کنار هم قرار بگیرند. (با integer programming حل کنید.)

حل من این بود که هر درایه ماتریس را یک متغیر می‌گیریم و مقادیر اولیه را به صورت قیود تساوی می‌گذاریم.

یک سری متغیر دیگر هم تعریف می‌کنیم که معادل جا به جا کردن هر دو ستون باشند.

برای اینکه یک‌ها کنار هم باشند هم باید متغیرهایی که تعریف کرده‌ایم به ازای یکی از حالت‌های تقسیم هر سطر به دو قسمت یک بخش ۱ داشته باشند. برای اینکه یکی از این شرط ها برقرار باشد می‌توانیم به ازای آنهایی که ۱ هستند یکی کم کنیم در این صورت حالت درست معادل ۰ می‌شود و اگر همه را در هم ضرب کنیم و صفر شود جواب دارد در غیر این صورت جواب ندارد.

برش بیشینه با semidefinite programming

هر متغیر را با ۱ یا -۱ می‌گذاشتیم و اگر در دو دسته‌ی مختلف می‌افتادند جواب -۱ می‌شد در غیر این صورت ۱ می‌شد. آخر اثبات که سر کلاس ننوشتیم:

اینجا فقط حالت متوسط را ثابت کرده است و اگر بخواهیم می‌توانیم احتمال رخ دادن آن را هم حساب کنیم و با مانتی‌کارلو آن را با افزایش زمان الگوریتم بهبود بدهیم.

الگوریتم تقریبی (قسمت دوم)

http://www.cse.buffalo.edu/~hungngo/classes/2006/594/

سوالات میان ترم تقریبی

Combinatorial Optimization 2012

http://dcg.epfl.ch/page-84766-en.html

سوال کتاب وزیرانی

سوال ۹.۱. مثال بد برای الگوریتم first-fit برای مسأله‌ی bin-packing

برش بیشینه با روش غیرتصادفی‌کردن

تفاوت جزوه و مباحث الگوریتم تقریبی

من جزوه‌ی الگوریتم تقریبی را که چک کردم در این قسمت با کتاب تفاوت داشت. البته قضیه 9.2 کتاب این را گفته است اما توضیح این بهتر است.