فصل 5 وزیرانی: k-مرکز

تعریف مساله k-مرکز: مجموعه ای از شهرها و فاصله ی بین هر دو شهر داده شده است. k شهر را انتخاب کنید و در آنها انبار بسازید که حداکثر فاصله ی هر شهر تا نزدیک ترین انبار به آن مینیمم شود.

این مساله و مساله ی وزن دار آن را با شرط برقرار بودن نامساوی مثلث حل می کنیم. بدون این شرط مساله قابل تقریب زدن نیست (مگر اینکه p=np باشد).

تکنیکی که برای حل مسائل این فصل استفاده می شود "هرس پارامتری" نام دارد. در فصل 17 از این تکنیک به همراه LP استفاده می کنیم.

مساله k-مرکز متریک: گراف کامل بدون جهت با یالهای وزندار که در نامساوی مثلث صدق می کنند (گراف G) و عدد صحیح مثبت k داده شده است. زیرمجموعه ای از رئوس (زیرمجموعه S) و هر راس دلخواهی از گراف را در نظر بگیرید، connect(v,S) را هزینه ی سبکترین یال از v به یک راس از S تعریف می کنیم. مساله پیدا کردن زیرمجموعه ی S ای است که |S|=k و عبارت زیر را مینیمم کند:

max_v (connect(v,S))

*هرس پارامتری برای حل مساله k-مرکز متریک

اگر هزینه ی جواب بهینه را بدانیم، می توانیم قسمت های زائد ورودی را هرس کنیم و مساله جستجو برای جواب را ساده تر کنیم. البته به دست آوردن هزینه ی جواب بهینه معمولا قسمت اصلی حل کردن مساله است. تکنیک هرس پارامتری به این صورت این مشکل را حل می کند: یک پارامتر t انتخاب می شود، که می تواند به عنوان حدس جواب بهینه در نظر گرفته شود. برای هر مقدار t، مساله داده شده (I) با حذف قسمت هایی که در هیچ جوابی با هزینه ی بیشتر از t هرس می شود. نسخه ی هرس شده را I(t) بنامید. الگوریتم از دو مرحله تشکیل شده است: 1) از یک خانواده از نمونه های I(t) برای محاسبه ی کران پایین جواب بهینه استفاده می شود (t*). در قدم دوم یک جواب برای نمونه ی I(a.t*) به دست می آید (برای a مناسب).

بیان مجدد مساله k-مرکز با هرس پارامتری: یالهای گراف G را به ترتیب از وزن کمتر به بیشتر مرتب می کنیم. گراف Gi را با همان مجموعه رئوس G و مجموعه ی i یال سبکتر G تعریف می کنیم. یک مجموعه ی غالب (dominating set) در گراف بدون جهت را زیرمجموعه ای S از رئوس تعریف می کنیم که هر راس خارج از این مجموعه مجاور یک راس در مجموعه S باشد. قرار دهید dom(H) را اندازه ی مجموعه غالب با کمترین تعداد اعضا. محاسبه ی dom(H) یک مساله np-سخت است. مساله k-مرکز معادل پیدا کردن کوچکترین اندیس i است که Gi یک مجموعه غالب با اندازه ی حداکثر k باشد؛ یعنی Gi شامل k گراف ستاره (دوبخشی کامل 1وp که p>1) باشد که همه ی راسها را می پوشاند. اگر i* را کوچکترین اندیس با این شرایط بگیریم، هزینه ی cost(ei*) هزینه ی k-مرکز بهینه است. {یالی که در آخرین مرحله اضافه می شود، ماکسیمم فاصله تا نزدیک ترین مرکز است.}. ما این هزینه را با OPT نشان می دهیم. خانواده ای که با آن کار می کنیم، گرافهای G1,..,Gm هستند.

مربع گراف H را تعریف می کنیم: گرافی که در آن بین دو راس یال هست، اگر در گراف اولیه بین آنها مسیر به طول حداکثر 2 وجود داشته باشد. به این گراف H^2 می گوییم.

ساختار زیر روشی برای پیدا کردن کران پایین برای OPT می دهد.

لم: گراف H داده شده است، I را یک مجموعه مستقل (زیرگراف تهی) از H^2 فرض کنید. در این صورت |I| <= dom(H).

اثبات: فرض کنید D مجموعه غالب در H باشد. آنگاه H شامل |D| ستاره است که همه ی راسها را می پوشانند. چون هر کدام از این ستاره ها یک خوشه(زیرگراف کامل) در H^2 می شوند، H^2 شامل |D| زیرگراف کامل است که تمام راسها را می پوشانند. بدیهی است که I حداکثر می تواند یک راس از هر زیرگراف کامل بردارد، پس لم برقرار است.

*الگوریتم k-مرکز متریک

1) گرافهای G1^2,..,Gm^2 را بسازید.

2) مجموعه مستقل ماکسیمال در هر کدام از گرافهای Gi^2 را بسازید (Mi).

3) کوچکترین اندیس i را برگردانید که |Mi| <= k باشد. (اندیس j-ام)

4) Mj را به عنوان جواب برگردانید.

*کران پایین الگوریتم:

لم: به ازای j تعریف شده در الگوریتم، cost(ej) <= OPT. (که ej همان طور که قبلا تعریف کردیم j-امین کوچکترین یال است).

اثبات: به ازای هر i<j داریم |Mi|>k است. {چون j اولین اندیسی است که |Mj| <= k}. طبق لم dom(Gi)>k و در نتیجه i* > i. پس j<=i*.

قضیه: ضریب تقریب الگوریتم قبل برای k-مرکز 2 است.

اثبات: مشاهده ی اصلی این است که مجموعه مستقل ماکسیمال I در گراف، یک مجموعه غالب هم هست (اثبات: برهان خلف: اگر راسی باشد که توسط I پوشش داده نشده باشد، آن را می توان به I اضافه کرد و جواب باز هم یک مجموعه مستقل خواهد بود که اندازه ی بیشتری دارد که با ماکسیمال بودن I تناقض دارد). پس در Gj^2 گراف های ستاره وجود دارند که مرکز آنها روی راسهای Mj است و همه ی راسها را پوشش می دهند. طبق نامساوی مثلث، وزن هر یال که در ساخت ستاره ها استفاده شده حداکثر دو برابر وزن یال ej است. پس قضیه با کمک لم قبل ثابت می شود.

حالا نشان می دهیم که 2 بهترین ضریب برای مساله k-مرکز متریک است.

قضیه: اگر p=np نباشد، هیچ الگوریتم چندجمله ای به ضریب بهتر از 2-epsilon برای مساله k-مرکز متریک نمی رسد.

اثبات: نشان می دهیم چنین الگوریتمی می تواند مساله dominating set را در زمان چندجمله ای حل کند. ایده آن مشابه اثبات فصل قبل است و شامل کاهش از مساله k-مرکز به مساله dominating set است. فرض کنید گراف G یک نمونه از مساله dominating set باشد. گراف کامل G' را به این صورت بسازید که راسهای آن همان رئوس G باشد و هر یال G در آن وزن 1 و هر یال دیگر وزن 2 داشته باشد. بدیهی است که G' در نامساوی مثلث صدق می کند. این کاهش در شرایط زیر صدق می کند:

- اگر dom(G) <=k باشد، G' یک k-مرکز با هزینه 1 دارد.

- اگر dom(G) >k بود، هزینه بهینه k-مرکز برای G' مقدار 2 است.

در حالت اول، وقتی روی G' الگوریتم را اجرا می کنیم، یک 2-epsilon تقریب است پس باید جواب 1 بدهد پس نمی تواند شامل هیچ یال با وزن 2 باشد. پس با استفاده از این الگوریتم می توانیم بین دو حالت ممکن تمایز قائل شویم، در نتیجه مساله dominating set را حل کنیم.

----------------------------------------------------------------------------------------------------------------------------------------------------

نسخه وزن دار

از تکنیک هرس پارامتری برای به دست آوردن الگوریتم با ضریب تقریب 3 برای تعمیم زیر از مساله k-مرکز استفاده می کنیم.

مساله k-مرکز وزن دار: علاوه بر تابع وزن روی یالها، یک تابع وزن روی راسها تعریف می کنیم و یک کران W. مساله باید زیرمجموعه ای از رئوس را بردارد که وزن آنها حداکثر W باشد و همان تابع هزینه ی قبلی را مینیمم کند:

max_v_V (min_u_S(cost(u,v)))

فرض کنید wdom(G) وزن dominating set با کمترین وزن را در G نشان دهد. پس با توجه به تعریف Gi، باید کوچکترین اندیسی را پیدا کنیم که wdom(Gi) <= w باشد. اگر i* این اندیس باشد، آنگاه هزینه جواب بهینه OPT=cost(ei*) است.

یک گراف با رئوس وزندار H داده شده، I را مجموعه مستقل H^2 فرض کنید. برای هر u عضو I قرار دهید s(u) = کم وزن ترین همسایه u در H که خود u هم می تواند همسایه ی خودش باشد. (توجه کنید که همسایه از H به دست می آید نه از H^2). مجموعه S را مجموعه همه ی همسایه های رئوس I قرار دهید. حقیقت زیر متناظر لم 5.2 برای به دست آوردن کران پایین به کار می رود.

لم:

w(S) <= wdom(H)

اثبات:

D را dominating set با کمترین وزن برای H فرض کنید. آنگاه مجموعه ای از ستاره های مجزا در H وجود دارد که راسهای آن رئوس D هستند و همه ی راسها را پوشش می دهند. چون هر کدام از این ستاره ها یک زیرگراف کامل در H^2 خواهند بود، I می تواند حداکثر یک راس از هر کدام بردارد. پس هر راس در I مرکزی از ستاره متناظر را به عنوان همسایه دارد. پس w(S) <=w(D).

در الگوریتم زیر si(u) کم وزن ترین همسایه u در Gi را مشخص می کند و خود u هم می تواند همسایه خودش باشد.

الگوریتم 5.10: k-مرکز متریک وزن دار

1) گرافهای G1^2,...,Gm^2 را بسازید.

2) در هر کدام از Gi^2 ها مجموعه مستقل ماکسیمال Mi را محاسبه کنید.

3) Si را که اجتماع si(u) ها به ازای هر u عضو Mi است حساب کنید.

4) کمترین اندیس i را که w(Si) <= W باشد را پیدا کنید. (j)

5) Sj را برگردان.

قضیه: ضریب تقریب الگوریتم بالا = 3