جواب سوال ۱ تمرین الگوریتم تقریبی

http://www.cs.uu.nl/research/techreps/repo/CS-1997/1997-39.pdf

واقعاً اینکه نسبت جوابها خود پارامتر مسأله بشود را هم می‌گویند unbounded؟ من فکر می‌کردم باید حتماً بینهایت بشود ولی در خود مقاله هم این طوری گفته.

LP-based approximation algorithms for capacitated facility location

دریافت
حجم: 197 کیلوبایت

توضیحات: http://link.springer.com/article/10.1007%2Fs10107-010-0380-8

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

http://www.ti.inf.ethz.ch/mb/projects/

facility location example

http://www2.informatik.hu-berlin.de/alcox/lehre/lvws1011/coalg/facility_location.pdf

مثالش غلطه که! :)) این عین کتاب وزیرانی هم هست...

من ایمیل زدم به تی‌ای عزیزمون پرسیدم:

مثال صفحه‌ی ۲۳۹ کتاب وزیرانی غلط است؟ چون اگر به مرکز facility دوم یک دایره به شعاع یک بزنیم، همه‌ی شهرها روی آن می‌افتند. می‌دانیم c1 از f1 هم فاصله‌ی ۱ دارد، در نتیجه فاصله‌ی f1 از نقاط دایره به مرکز f2 حداکثر در یک نقطه ۳ می‌شود. (در حالتی که دو دایره مماس باشند و c1 نقطه تماس باشد سر دیگر قطر تنها نقطه به فاصله ۳ خواهد بود.)

امتحان‌ها

من از زمان تحویل تمرین دکتر آبام نهایت تشکر را دارم! تنها دلیلی بود که من فهمیدم که امتحان‌هام توی خرداده نه تیر! (فقط هندسه توی تیره)

اولین امتحان تقریبی است که ۲۲ است بعدی موازی است که ۲۷ است بعدی ۳ تیر هندسه محاسباتی پیشرفته است.

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

ایده‌ای که از همه جالب‌تر بود این است که یک تابع کران برای الگوریتم به دست می‌آوریم. بعد بر اساس توانهای اپسیلون (یا ضریب تقریب دیگر) آن را بازه‌بندی می‌کنیم. این کار باعث می‌شود خطای جمعی ما ضریب اپسیلون باشد. در نتیجه‌ی این کار جوابی که به دست می‌آید به دلیل اینکه از تابع کران استفاده کردیم تقریب مورد نظر ما خواهد بود.

ایده‌ی دیگری که دیدم این بود که فضای مسأله را بر اساس هزینه‌ی آن به صورت یک چندوجهی صعودی/نزولی اکید ذخیره می‌کردند. حتی به صورت ساختمان داده مربوط به آن مسأله خاص.

چیز جدید دیگری که دیدم این بود که نامساوی مثلث را برای یک semidefinite programming به صورت برداری نوشته بودند:

(vi-vj)(vi-vk) >= 0

که هیچ ایده‌ای ندارم چه ربطی به نامساوی مثلث دارد؟

facility location

http://www.cs.cornell.edu/People/mpal/papers/UFL_ESA2003.ppt

اسلایدهای ارائه‌ی سر کلاس تقریبی بچه‌ها

مرجع: http://mahdian.org/pub.html

روش‌های FPT

الآن فهمیدم در واقع چیزی که برای الگوریتم تقریبی ارائه دادم مجموعه‌ای از روشهای FPT بوده.

الآن فهمیدم که برای هندسه محاسباتی پیشرفته هم چیزی که ارائه دادم FPT بوده! loosing weight از نوع bounded search tree بوده!

دوگان LP بدون ماتریس

بالاخره فهمیدم باید چه کار کنم! :))

بعد از اینکه به فرم استاندارد در آوردیم:

اول طرفین هر نامساوی را در یک متغیر جدید ضرب می‌کنیم. بعد مسأله را ماکسیمم به مینیمم (یا برعکس) تغییر می‌دهیم و قیدها را به این صورت تغییر می‌دهیم که به جای یک طرف نامساوی ضریب هر کدام از متغیرهای قبلی و به جای طرف دیگر ضریب آن در تابع هدف را می‌گذاریم.

http://en.wikipedia.org/wiki/Linear_programming#Another_example

اشکال تمرین تقریبی ۲

سوال ۳ تمرین را با روش وزیرانی نمی‌شود حل کرد چون اینجا الآن نمی‌توانیم مطمئن باشیم که دقیقاً ۲ تا متغیر داریم! (فکر کنم سوالش غلط است)

همین مسأله را به روش دیگری LP برایش نوشته و حل شده است اما در صورت سوال ما گفته است که این طوری باید بنویسید.