تمرین های فصل 2 الگوریتم تقریبی -وزیرانی

1- یک گراف بدون جهت داده شده است، برش با بیشترین تعداد یال را پیدا کنید. الگوریتم حریصانه ی زیر را در نظر بگیرید: در هر مجموعه دو راس دلخواه قرار می دهیم، راسهای بعدی را به مجموعه ای اضافه می کنیم که تعداد یالهای بیشتری بین این راس و اعضای آن مجموعه است. نشان دهید الگوریتم 1/2 تقریبی است و برای آن یک مثال tight بدهید. از چه کران بالایی برای جواب بهینه استفاده کردید؟ دو مثال از گرافهایی بدهید که به ازای آنها این کران بالا دو برابر بدتر از جواب بهینه باشد. مساله و الگوریتم را به حالت وزندار تعمیم دهید.

?) 1/2 OPT <= ALG <= OPT

deg(Vi) >= deg_A(Vi)+deg_B(Vi)

ALG(Vi) = max( deg_A(Vi), deg_B(Vi) )

max(x,y) >= 1/2(x+y)

ALG(Vi) >= 1/2 ( deg_A(Vi)+deg_B(Vi) ) >= 1/2 deg(Vi)

OPT(Vi) = deg_A*(Vi) <= deg(Vi)

ALG = sum(ALG(Vi)) >= 1/2 sum(deg(Vi)) >= 1/2 OPT

مثال: دو گراف ستاره را راسهای غیرمرکزشان را یکی کنید. فرض کنید دو راس دلخواهی که الگوریتم انتخاب می کند دو راس مرکز ستاره های سابق باشد. نصف یالها در این حالت به عنوان جواب الگوریتم برگردانده می شوند. جواب بهینه این است که راسهای مرکز در یک مجموعه باشند و راسهای غیرمرکز در مجموعه ی دیگر باشند. در این حالت همه ی یالها برگردانده می شوند.

(ایده: اجرای الگوریتم و انتخاب بدترین حالت ممکن در هر مرحله)

کران بالا:

مثال کرانها:

2- سوال قبل را با الگوریتم جستجوی محلی (local search) حل کنید: از دو مجموعه ی دلخواه شروع کنید، اگر با عوض کردن جای یک راس جواب بهتر شد این کار را انجام دهید. تا وقتی که دیگر نشود این کار را ادامه داد. ثابت کنید در زمان چندجمله ای الگوریتم تمام می شود (تعداد مراحل چندجمله ای است) و ضریب تقریب 1/2 است.

برای اثبات ضریب تقریب که همان اثبات سوال قبل است فقط دیگر قسمت اینکه جواب فعلی و جواب بعدی را نمی خواهد. (به جای جدا کردن روی A و B مستقیما می نویسیم درجه بزرگتر از نصف می شود.)

برای اثبات تعداد مراحل هر بار جواب دارد بهبود پیدا می کند و حداقل هزینه ی شروع و جواب بهینه اختلافشان تقسیم بر جوابی که هر بار بهبود پیدا می کند چند جمله ای می شود.

3- در یک گراف وزن دار برش با وزن بیشینه که گراف را k قسمت کند پیدا کنید. الگوریتم حریصانه با ضریب (1-1/k) بدهید. آیا این جواب tight است؟

انتخاب حریصانه: سود برداشتن / هزینه ی برداشتن

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

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

cost(Vi, Sj) = sum_u_in_Sj( cost(u,Vi) ) / sum_u_not_in_Sj( cost(u,Vi) )

ALG(Vi) = max_Sj ( cost(Vi, Sj) ) <= 1/k sum_j (cost(Vi,Sj) )

W(Vi) = sum of weights of incident edges of Vi

sum_j(cost(Vi,Sj)) <= k*W(Vi)-W(Vi) = (k-1)W(Vi)

OPT(Vi) < W(Vi)

==> ALG < (k-1)/k OPT

مثال:

4- برش با وزن بیشینه جهت دار. الگوریتم با ضریب تقریب 1/4 بدهید.

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

(راه حل 2: local search)

ALG(Vi) = max( sum_u_S' (cost(Vi,u) , sum_u_S (cost(Vi,u)) )

ALG(Vi) >= 1/2 sum_u (cost(Vi,u))

ALG >= 1/2 sum_Vi sum_u(cost(Vi,u))

OPT <= sum_Vi sum_u( cost(Vi,u) )

ALG >= 1/4 OPT

5- با کمک سوال 2 (local search) و این حقیقت که برای گرافهای دوبخشی مساله پوشش راسی در زمان چندجمله ای حل می شود، یک الگوریتم تقریبی با ضریب lg delta بدهید که delta بیشترین درجه ی راسهای گراف است.

راهنمایی: زیرگراف به دست آمده برای سوال برش بیشینه را در نظر بگیرید (H). می دانیم H دوبخشی است و درجه ی هر راس آن از نصف درجه ی آن راس در G (گراف اصلی) بیشتر مساوی است.

می توانیم از تکنیک لایه ای استفاده کنیم و گراف H را هر بار بسازیم و یالهایی که تصمیم گرفتیم براشون رو حذف کنیم. هر بار نصف درجه ی راسها را بر می داریم حداقل، پس تقریب حداکثر log delta می شود.

6- رنگ آمیزی رئوس: گراف بدون جهت G داده شده، راسهای آن را طوری رنگ کنید که حداقل تعداد رنگ به کار برود و دو سر هر یال رنگ متمایز داشته باشند.

الف) یک الگوریتم حریصانه بدهید که G را با delta+1 رنگ، رنگ کند. (delta ماکسیمم درجه)

ب) یک الگوریتم برای گرافهای سه رنگ پذیر بدهید که O(sqrt(n)) رنگ بخواهد.

راهنمایی: برای هر راس، گراف القایی روی همسایه های آن، N(v)، دوبخشی است پس به صورت بهینه قابل رنگ کردن است. اگر v درجه ی بیشتر از sqrt(n) داشته باشد، v و همسایه هایش را با سه رنگ متمایز رنگ کنید. این کار را ادامه دهید تا هر راس درجه ی کمتر از sqrt(n) داشته باشد. بعد از الگوریتم بخش اول استفاده کنید.