حراج دومین قیمت

یک سمینار در مورد این توی دانشگاه بود یه سری شکلات تابلرون هم جایزه می دادن! الآن دیدم توی اسلایدهای الگوریتم تقریبی هست.

http://algo2.iti.kit.edu/appol/les8.pdf

اصلاحیه

چیزی که من در پست TSP دور ترجمه کردم "گشت" بوده.

http://algo2.iti.kit.edu/appol/tsp.pdf

بدتر از اون چیزیه که توی گزارش ام نوشتم :)) wlog می شده without loss of generality بعد من مطمئنم یه چیز دیگه ترجمه کردم.

این اسلایدها یکم آلمانی داره ولی شکل های خوبی داره و درست توضیح داده:

http://algo2.iti.kit.edu/appol

bin packing and job scheduling

http://algo2.iti.kit.edu/appol/les7.pdf

bin packing

http://www.cs.ucr.edu/~neal/2006/cs260/piyush.pdf

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

http://sharif.edu/~msafari/courses/approx882/notes/

رند کردن LP و رند کردن تصادفی

ایده ی رند کردن LP نوشتن برنامه به صورت یک LP برای اعداد صحیح و حل کردن آن برای LP های معمولی است و بعد جا به جا کردن جواب آن به نقطه ی صحیح نزدیک به آن در ناحیه جواب. قسمت سخت این کار رند کردن است که باید بشود برای suboptimality آن یک کران پیدا کرد.

(بقیه اش رو توی اسلاید هندسه بعد از قسمت سوالها نوشته بودم قبلا.)

درخت steiner

تعریف مساله ی درخت steiner: یک گراف وزن دار و زیرمجموعه ای از راسهای آن T داده شده است. درخت با کمترین هزینه را پیدا کنید که همه ی راسهای T را به هم وصل می کند. ("راسهای کمکی" راسهایی هستند که در گراف هستند اما در T نیستند.)

مساله: یک گراف وزن دار و زیر مجموعه ای از راسهای آن داده شده R، می خواهیم حداقل هزینه ی اتصال زیرگراف پوشای R را به دست بیاوریم. راسهای R را پایانی و بقیه راسهای گراف را استینر می نامیم.

نکته 1: زیرگراف پوشای R یک درخت است. (اگر نباشد می توانیم از آن یال حذف کنیم و هزینه کم شود اما همبندی حفظ می شود.)

نکته 2: می توانیم از راسهای غیرپایانی (استینر) برای به دست آوردن درخت استینر استفاده کنیم.

ادعا 1: بدون از دست رفتن عمومیت می توانیم فرض کنیم گراف اولیه ما (G) گراف کامل است.

Gc: تکمیل فاصله ای گراف G: هزینه ی یال u به v را به ازای هر زوج راس گراف طول کوتاهترین مسیر بین آنها در G قرار می دهیم. هزینه ی یالهای Gc یک فاصله است. (4 خاصیت فاصله را دارد.)

لم 1: اگر T درخت پوشای R در Gc باشد، می تواینم زیردرختی در G پیدا کنیم T' که R را بپوشاند و هزینه ی آن کمتر از هزینه ی T در Gc باشد.

هر یال T' یک مسیر در G است پس اجتماع یالهای این مسیرها یک گراف می شود که هزینه ی آن همان هزینه ی T' است. پس روی آن می توانیم یک درخت مثل T بسازیم و هزینه ی آن کمتر خواهد بود.

برای حل از به دست آوردن کران پایین شروع می کنیم. ایده ی دور فروشنده ی دوره گرد را برای به دست آوردن کران پایین برای درخت استینر بهینه استفاده می کنیم.

لم: فرش کنید Gc(R) زیرگراف القایی توسط R از Gc باشد. هزینه ی MST روی Gc(R) حداکثر به اندازه ی هزینه ی دور فروشنده ی دوره گرد بهینه روی Gc(R) است.

(اثبات: به پست فروشنده دوره گرد مراجعه کنید!)

لم: هزینه ی دور فروشنده ی دوره گرد (TSP) بهینه روی Gc(R) حداکثر دو برابر OPT (درخت استینر متناظر R روی گراف Gc(R) ) است.

اثبات: 

(ادامه دارد..! در ضمن اسم درست این درخت اشتاینر بود نه استینر! )

الگوریتم های بهینه برای خوشه بندی تقریبی

فاصله درون خوشه ای:

1- حداکثر فاصله بین نقاط درون یک خوشه (فاصله زوج نقاط: بدون مرکز)

2- حداکثر فاصله بین نقاط درون یک خوشه و مرکز خوشه (دارای مرکز)

الگوریتمی که ضریب تقریب بهتری از 2 داشته باشد برای ابعاد 2 و بالاتر وجود ندارد مگر اینکه P=NP باشد. الگوریتم با زمان O(nlogk) داریم که طبق algebraic decision tree بهینه است. اگر (حداکثر) اندازه ی خوشه مشخص باشد تعداد خوشه ها را با تقریب 1+epsilon خواهیم داشت.

از گونه های دیگر مساله مرکزهای ممنوعه، مساله تامین کنندگان و مساله تامین کنندگان وزن دار است که با زمان O(nlogk) به جواب بهینه یا نزدیک بهینه تقریبی می رسند.

الگوریتم تقریبی: فروشنده دوره گرد دارای فاصله

فروشنده دوره گرد: در یک گراف وزن دار دور با کمترین وزن را پیدا کنید که هر راس را دقیقا یک بار ببیند. (دور همیلتونی)

فروشنده دوره گرد با فاصله: در یک گراف وزن دار دور با کمترین وزن را پیدا کنید که هر راس حداقل یک بار دیده شده باشد.

دلیل نام گذاری فروشنده دوره گرد با فاصله این است که اگر گراف دیگری بسازیم که بین دو راس آن یک یال با وزن کوتاهترین فاصله بین این دو راس باشد، اگر گراف اولیه همبند باشد تشکیل یک تابع فاصله می دهد.

تابع فاصله:

1) فاصله دو راس نامنفی است

2) اگر فاصله یک راس تا راس دیگر 0 باشد دو راس یکی هستند

3) تقارن

4) نامساوی مثلث

این یک مساله کمینه کردن است. پس دنبال کران برای OPT می گردیم. چند تا از ایده های ممکن MST و قطر گراف و مسیر فروشنده دوره گرد (مسیر همیلتونی با کمترین وزن) هستند.

برای چک کردن اینکه کدام یک از این معیارها خوب هستند به این نکته توجه می کنیم که کدام بیشتر به جواب نزدیک می شود. یعنی اگر یک ویژگی را انتخاب کنیم که برای یک ورودی بزرگ 100 برابر جواب بهینه باشد ضریب تقریب ما از 100 بهتر نمی شود. مثلا قطر در حالتی که گراف دارای یالهای با وزن مساوی باشد n برابر جواب بهینه می شود که خوب نیست.

نکته ی دیگری که در انتخاب معیار هست ساده تر بودن از محاسبه ی جواب بهینه است. مسیر فروشنده دوره گرد ساده تر نیست.

اما MST با کمترین وزن را راحت می شود به دست آورد پس سعی می کنیم از آن استفاده کنیم.

اگر روی MST گراف dfs بزنیم می بینیم:

ALG = 2*MST <= 2*OPT

یعنی یک جواب 2-تقریبی از فروشنده دوره گرد با فاصله است.

آیا می شود این تحلیل را بهتر کرد؟

نه، چون می شود ورودی هایی مثال زد که حالت تساوی اتفاق می افتد. مثل: گراف خط. (هر راسی به راس بعدی وصل است جز آخری). یعنی داریم:

opt(I) = 2(n-1)=2f(I)

از این نتیجه می گیریم با معیار MST به جواب بهتری نمی رسیم اما با روشهای دیگر ممکن است برسیم.

در واقع کاری که ما اینجا کردیم این بود که MST رو به گراف اویلری تبدیل کردیم (گرافی که بدون برداشتن دست از روی کاغذ بتوانیم رسم کنیم) و از این استفاده کردیم که یک دور اویلری داریم. اگر بتوانیم به روش بهتری MST را به گراف اویلری تبدیل کنیم به ضریب تقریب بهتری می رسیم.

یک دور اویلری وجود دارد اگر و تنها اگر هر راسی درجه زوج داشته باشد (با این فرض که از یک راس شروع کنیم و به همان راس برگردیم). پس اگر یک matching بین همه ی گره های با درجه فرد در MST پیدا کنیم و این یالها را به درخت اضافه کنیم مساله حل می شود.

تطابق بیشینه ی با کمترین وزن گراف را به دست بیاورید و راسهای با درجه ی زوج آن را در نظر بگیرید، وزن آن کمتر مساوی نصف وزن دور TSP با کمترین هزینه روی گراف است.

اثبات: به دلیل خاصیت فاصله، وزن دور TSP روی راسهای تطابق بیشینه با کمترین وزن، کمتر مساوی OPT است. این دور شامل دو تطابق می شود (می توانیم یالهایی که نگه می داریم با آنهایی که نگه نمی داریم جا به جا کنیم!)، تطابق کوچکتر حداکثر نصف جواب بهینه وزن دارد.

الگوریتم: فروشنده دوره گرد با فاصله

M: درخت پوشای کمینه (MST) روی G

U: مجموعه راسهای درجه زوج M

P: مینیمم هزینه ی تطابق کامل U با بقیه راسهای G

دور اویلری روی M اجتماع P را برگردان.

قضیه: الگوریتم بالا 3/2 تقریبی است برای فروشنده دوره گرد با فاصله.

اثبات:

تعداد راسهای با درجه فرد در MST باید زوج باشد، پس یک تطابق کامل روی این راسها انجام می دهیم تا گراف اویلری داشته باشیم.

گفتیم هزینه ی تطابق کامل کمتر مساوی 1/2 OPT است پس:

alg <= MST+matching <= 3/2OPT

نکته: در اثبات از دو کران پایین استفاده کردیم. هر کدام به تنهایی کافی نیستند اما ترکیب آنها با هم نتیجه خوبی می دهد.

الگوریتم تقریبی: پوشش راسی

تقریب مساله ی پوشش راسی بهتر از o(logn) که n تعداد راسها باشد وجود ندارد مگر اینکه P=NP باشد.

مهمترین قدم در به دست آوردن الگوریتم تقریبی به دست آوردن جواب بهینه است که معمولا برای به دست آوردن جواب هم کافی است. در مورد مساله پوشش راسی این اتفاق می افتد.

صورت مساله: یک گراف بدون جهت داریم، کوچکترین زیر مجموعه از راسها را پیدا کنید که حداقل یک سر هر یال در این مجموعه باشد.

فرض کنید الگوریتمی داریم که تعداد راسهای جواب بهینه را می دهد. می توانیم از این تابع برای به دست آوردن جواب بهینه استفاده کنیم.

ایده: حذف یک راس چه تاثیری روی اندازه ی جواب بهینه دارد؟

اگر بعد از حذف آن راس تعداد اعضای جواب تغییر نکرد این راس از اول زیادی بوده است، اما اگر کم شد یعنی جزو جواب است و به زیرمجموعه منتخب اضافه می شود.

وقتی تعداد راسهای منتخب ما صفر شد الگوریتم تمام می شود.

به این ویژگی که بتوان یک مساله را به یک زیرمساله ی مشابه مساله ی اصلی تبدیل کرد خود کاهش پذیری (self reducibility) می گوییم.

معمولا اثبات اینکه یک الگوریتم جوابی می دهد که از a برابر جواب بهینه کمتر است ساده نیست، پس از کران پایین آن استفاده می کنیم. می توانیم برای یک ورودی تابع ویژگی را تعریف کنیم که مقدار آن از هزینه ی جواب بهینه کمتر باشد و ثابت کنیم:

ALG(I) <a*f(I) <a*OPT(I)

برای مساله ی پوشش راسی می توانیم زیرمجموعه ای از یالها را در نظر بگیریم که راس مشترک ندارند. چون هر پوشش راسی باید یک سر این یالها را داشته باشد پس هزینه ی پوشش راسی از تعداد یالهای این مجموعه بیشتر مساوی است. یعنی اندازه ی هر پوشش راسی بیشتر مساوی هر تطابق (matching) است.

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

گفتیم که vertex cover بهینه تعداد راس بیشتری از تعداد یالهای maximum matching دارد و طبق الگوریتم ما راسهای بین یالهای این matching همه قابل پوشش هستند. چون تعداد راسهای matching دو برابر تعداد یالهای آن است پس ضریب تقریب 2 می شود.