ادامه سوالات فصل 2 وزیرانی

9- یک الگوریتم حریصانه که ضریب تقریب H(n) برای پوشش چندگانه مجموعه ای بدهید. پوشش چندگانه مجموعه ای تعمیمی از پوشش مجموعه ای است که در آن نیازمندی های پوشش عدد صحیح هم برای هر عضو داده شده است و مجموعه ها می توانند چندین بار انتخاب شوند تا همه ی نیازمندی ها را پاسخگو باشند. فرض کنید هزینه ی برداشتن a کپی از مجموعه S_i برابر a.cost(S_i) باشد.

حل:

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

تکنیک لایه ای ضریب تقریب را تغییر نمی دهد.

10- با یک مثال tight مناسب نشان دهید که تحلیل الگوریتم 2.2 نمی تواند بهبود یابد، حتی در حالتی که اعضای پوشش مجموعه ای در نظر گرفته شود. یعنی هزینه ی مجموعه ها 1 باشد.

راهنمایی: الگوریتم حریصانه را روی یک نمونه پوشش راسی اجرا کنید.

حل:

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

(ضریب تقریب: H(n))

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

مثال: همان مثال جزوه که گراف دو بخشی با r راس در قسمت بالا و r+r/2+..+1 راس در قسمت پایین بود.

11- الگوریتم زیر را برای مساله پوشش راسی وزن دار در نظر بگیرید. برای هر راس v، متغیر t(v) را با وزن آن مقدار دهی می کنیم و وقتی t(v) صفر شد راس را به پوشش اضافه می کنیم. c(e) مقداری است که به یال e نسبت داده شده است.

الگوریتم:

1- مقداردهی اولیه: C تهی، به ازای هر راس v از V قرار بده t(v) = w(v)، به ازای هر یال از E قرار بده c(e) = 0

2- تازمانی که C یک پوشش راسی نیست: یک یال پوشش داده نشده مثل (u,v) را بردار. m=min(t(u),t(v)) قرار بده.

t(u) = t(u)-m

t(v)=t(v)-m

c(u,v) = m

همه ی راسهایی که t(v) صفر دارند به C اضافه کن.

3- C را برگردان.

نشان دهید این الگوریتم ضریب تقریب 2 دارد.

راهنمایی: نشان دهید مجموع هزینه ی یالها برای جواب بهینه (OPT) یک کران پایین است و نشان دهید که وزن پوشش C حداکثر دوبرابر مقدار هزینه یالها است.

حل:

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

min(t(u),t(v)) = cost(e) <= t(u) <= w(u) , cost(e) <= t(v) <= w(v) ==> sum( cost(e) ) <= OPT

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

12- الگوریتم لایه ای برای پوشش راسی را در نظر بگیرید. تابع وزن دیگری که برای آن الگوریتم 2-تقریبی داریم تابع ثابت است: به سادگی از الگوریتم 2-تقریبی مساله پوشش راسی با کمترین تعداد راس استفاده می کنیم. آیا می شود با تکنیک لایه ای از این تابع به جای تابع وزن-درجه استفاده کرد؟

(تابع وزن-درجه: وزن هر راس ضریب ثابتی از درجه آن است.)

خیر، زیرا در این صورت راسی که وزن کمتری دارد انتخاب می شود و این یعنی انتخاب دلخواه رئوس!

مثال حالت بد: گراف ستاره با n برگ که همه برگها وزن n/2 داشته باشند و  راس مرکزی وزن n داشته باشد.

جواب الگوریتم: همه ی راسهای درجه 1 را بر می دارد.

جواب بهینه: فقط راس مرکزی را بردارد.

ضریب تقریب:

(n*n/2)/n=n/2

یعنی هیچ ضریب ثابتی برای تقریب آن نخواهد بود.

13- از تکنیک لایه ای استفاده کنید که الگوریتم تقریبی با ضریب f برای پوشش مجموعه ای بدهید که f تعداد تکرار پرتکرارترین عضو مجموعه مرجع است. یک مثال tight برای این الگوریتم بدهید.

برای هر عضو مجموعه مرجع مینیمم هزینه ی آن در هر مجموعه (هزینه مجموعه/تعداد اعضای مجموعه) را هزینه ی آن عضو قرار می دهیم. اعضای با هزینه مینیمم را انتخاب می کنیم. مجموعه های شامل این اعضا را حذف می کنیم و خود این اعضا را به جواب اضافه می کنیم و هزینه ی اعضای باقیمانده را حساب می کنیم.

اثبات ضریب تقریب: هر عضو حداکثر در f مجموعه می تواند انتخاب شود (اگر همه ی این مجموعه ها با هم انتخاب شوند) پس هزینه ی آن حداکثر f برابر می شود.

مثال حالت بد: 

{a,b,c} cost: 1

{a,b,c} cost: 1

alg=2*1=2, OPT=1, f=2

14- یک تورنمنت یک گراف جهتدار است که به ازای هر زوج راس u و v از آن دقیقا یکی از دو یال (u,v) و (v,u) در گراف هست. یک مجموعه راس فیدبک برای گراف زیرمجموعه ای از رئوس است که حذف آنها یک گراف بدون دور ایجاد می کند. یک الگوریتم با ضریب 3 برای پیدا کردن مجموعه رئوس فیدبک مینیمم در یک گراف جهتدار بدهید.

راهنمایی: نشان دهید کافی است همه ی دورهای به طول سه را از بین ببریم. از پوشش مجموعه ای ضریب f برای این کار استفاده کنید.

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

اثبات ضریب تقریب: هر کدام از یالهای هر دور را که حذف کنیم جواب است، اما در بدترین حالت همه ی یالهای دور را حذف می کنیم که سه برابر حذف یک یال است و این بدترین حالت است (جواب بهینه یک یال باشد و ما سه یال حذف کنیم) پس ضریب تقریب الگوریتم 3 است.

15- مساله پوشش بیشینه: یک مجموعه مرجع U از n عضو داده شده که هر کدام وزن نامنفی دارند. همچنین مجموعه ای از زیرمجموعه های U به نامهای S_1,...,S_L و عدد صحیح k داده شده است. k تا از مجموعه ها را بردارید طوری که وزن اعضای برداشته شده ماکسیمم شود.

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

1-(1-1/k)^k > 1-1/e

حل:

(هر عضو مجموعه مرجع یک وزن دارد، پس وزن هر مجموعه جمع وزن اعضای آن است اما وقتی اجتماع می گیریم دیگر وزن اعضای تکراری حساب نمی شود.)

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

؟؟

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

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

راهنمایی: مجموعه مرجع پوشش مجموعه ای شامل 2n عضو است: خود رشته و معکوس آن.

همان طور که راهنمایی گفته است معکوس رشته را هم به مجموعه ی رشته ها اضافه می کنیم و مثل قبل حل می کنیم.

ب) کوتاهترین رشته ای را پیدا کنید که یا خود رشته یا معکوس آن را داشته باشد.

راهنمایی: به جای مجموعه ی ابررشته های هر رشته که قبلا به کار می بردیم، ابررشته های خود رشته یا معکوس آن را در نظر بگیرید. خود این ابررشته را به طور مناسب انتخاب کنید.

ابررشته های خود رشته که شامل معکوس آن نیستند یا ابررشته های شامل معکوس رشته که شامل خود رشته نیستند.

(؟)