ادامه ی تمرینهای فصل 1 وزیرانی (الگوریتم تقریبی)

4- مساله پوشش راسی را حریصانه حل کنید: راس با بیشترین درجه را بردارید و همسایه های آن را حذف کنید. نشان دهید ضریب تقریب این الگوریتم O(log n) است و یک مثال tight برای آن بدهید.

راهنمایی: تحلیل شبیه قضیه 2.4 (اثبات set cover) است.

OPT <= ALG <= O(log n) OPT

اجزای مهم این مساله یالها هستند. (چون یک سر هر یال باید در پوشش راسی باشد.)

انتخاب یال i-ام (حریصانه): سود / هزینه

ALG(ei) = delta(i) <= OPT(n-i)/(n-i) <= OPT/(n-i)

ALG <= OPT*sum_i_1_n(1/(n-i)) <= OPT*O(log n)

 مثال tight: می خواهیم یک گراف دوبخشی بسازیم، چون انتخاب یک بخش آن جواب VC است.

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