3SUM

http://en.wikipedia.org/wiki/3SUM

APX

http://en.wikipedia.org/wiki/APX

Linear Programming III (ellipsoid algorithm)

http://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/LinearProgrammingIII.pdf

tree metric

فصل 5.8 ویلیامسون

ellipsoid method (برای بار هزارم!)

http://math.mit.edu/~goemans/18433S09/ellipsoid.pdf

ترکیبیات چندوجهی

http://math.mit.edu/~goemans/18433S13/polyhedral.pdf

هرس پارامتری به همراه LP

مرجع: فصل ۱۷ کتاب وزیرانی (سوال تمرین زمانبندی روی ماشین‌های مستقل)

اینجا LP برای مسأله جواب (تقریبی) نمی‌دهد (integrality gap نامحدود دارد یعنی نسبت جواب LP و جواب بهینه نامحدود است).

پس خودمان کاری می‌کنیم که تقریب مورد نظرمان اتفاق بیفتد. برای اینکه یک جواب تقریبی از جواب بهینه باشد، طبق مطالب فصل ۱ و ۲ باید تقریبی از کران مسأله باشد. در کمال بدبختی ما این کران را هم نداریم. برای همین یک پارامتر را می‌گیریم که بتواند کران مناسبی برای مسأله باشد (ولی نمی‌توانیم در زمان کمی حسابش کنیم) و روی آن مثلاً جستجوی دودویی (یا هر جستجوی دیگری!) به کار می‌بریم تا تقریبی از این پارامتر به دست بیاید. در نتیجه با تقریب زدن این پارامتر، می‌توانیم مسأله را هم تقریب بزنیم. (خلاصه اینکه در دو ضرب مسأله را حل می‌کنیم.)

البته از LP هم این استفاده را می‌کنیم که نقاط صحیح جواب را به دست بیاوریم و فقط دنبال بقیه جواب بگردیم.

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

چه زمانی جستجوی محلی برای تقریب زدن کار می‌کند؟ وقتی که جواب بهینه‌ی محلی و بهینه‌ی واقعی تقریبی از هم باشند. به این نسبت locality gap می‌گویند.

http://pages.cs.wisc.edu/~shuchi/courses/787-F09/scribe-notes/projects/project-notes-2.pdf

Vehicle routing problem

http://en.wikipedia.org/wiki/Vehicle_routing_problem

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

من سوال ۲ را از خود استاد پرسیدم حل آن با این روش است:

می‌توانیم همیشه یک جواب صحیح بسازیم که جواب بهینه باشد. برای این کار وزن هر یال را صفر می‌کنیم و به یکی از یالهای غیرصفر همسایه‌اش می‌دهیم. در این صورت چون دور فرد (و در نتیجه مثلث) نداریم جمع همچنان ثابت می‌ماند و جواب مسأله تغییر نمی‌کند و قیدی هم به هم نمی‌خورد. با این کار به یک جواب صحیح می‌رسیم، چون جمع یالهای مجاور هر رأس ۱ است. چون قید صفر بودن متغیر یک رأس اگر اتفاق بیفتد، سر دیگر یالهای متصل به آن باید ۱ شوند تا قیدهای مسأله به هم نخورد و در این صورت جمعشان ۱ می‌شود. در این صورت یک گراف دوبخشی ساخته می‌شود که جواب بهینه‌ی آن باید ۰و۱ باشد. پس جواب بهینه‌ی صحیح برای مسأله وجود دارد. اگر یک رأس در هر دو دسته باشد هم مشکلی پیش نمی‌آید، چون در این صورت همه‌ی قیدهای مکمل برقرار می‌شوند.