تمرین های WS فصل 5.1-5.3

فصل 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

تمرین های فصل 4

1- نشان دهید الگوریتم 4.3 می تواند به عنوان یک تابع برای پیدا کردن k-برش با ضریب 2-2/k از k-برش کمینه استفاده شود. چند فراخوانی تابع برای این کار لازم است؟

(الگوریتم 4.3: برش چندگانه: برای هر ترمینال (k تا کلا) برش ایزوله کمینه را پیدا می کند و اجتماع k-1 برش سبکتر را بر می گرداند.

برای پیدا کردن برش ایزوله همه ی راسهای دیگر را به صورت یک راس در نظر می گیرد و با شارش بیشینه برش کمینه آن را پیدا می کند.

ضریب تقریب: 2-2/k)

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

2- یک الگوریتم حریصانه معمولی برای محاسبه چندبرش این است: از گراف به ازای هر زوج ترمینالی که در یک مولفه همبندی هستند، برش s-t را به دست بیاوریم و کم وزن ترین آنها را حذف کنیم و این کار را ادامه بدهیم تا همه ی ترمینالها جدا شوند. ثابت کنید این الگوریتم ضریب تقریب 2-2/k دارد.

این مساله برعکس مساله قبلی است. چون کم وزن ترین برش در گراف کم وزن ترین برش در درخت گومری-هو هم هست، پس این کار معادل اجرای الگوریتم 4.7 برای k-برش کمینه است که ضریب تقریب 2-2/k دارد.

* سوالات مربوط به درخت گومری-هو:

3- فرض کنید گراف با یالهای وزندار نامنفی داده شده است. و f(u,v) وزن برش u-v کمینه بین این دو راس در گراف است.

1) اگر f(u,v) <= f(u,w) <=f(v,w) باشد، ثابت کنید f(u,v)=f(u,w).

حل: اگر دو راس را با یک برش از هم جدا کرده باشیم، هر دوی آنها نمی توانند به یک راس دیگر وصل باشند. در اینجا فرض کنید v و u را از هم جدا کرده باشیم، در این صورت حتما یا w-u یا v-w از هم جدا شده اند. پس

f(u,v) >= min(f(u,w),f(v,w)) = f(u,w)

f(u,v) <= f(u,w)

==> f(u,v) = f(u,w)

2) نشان دهید بین C(n,2) مقدار f(u,v) به ازای همه زوج رئوس، حداکثر n-1 مقدار متمایز است.

حل: هر برش رئوس را به دو قسمت ناتهی تقسیم می کند. پس هر بار حداقل یک راس جدا می شود. قسمت آخر هم که خود به خود وقتی بقیه جدا شده باشند جدا خواهد بود. پس حداکثر n-1 مقدار کمترین برش وجود دارد. اگر قسمت هایی که جدا می شوند، بیشتر از یک راس باشند به همین دلیل که راس آخر خود به خود جدا می شود، مقدار کمتر هم خواهد شد.

3) نشان دهید به ازای هر سه راس u و v و w داریم:

f(u,v) >= min( f(u,w), f(w,v) )

حل: به قسمت 1 نگاه کنید.

4) نشان دهید به ازای هر زیرمجموعه از رئوس داریم:

f(u,v) >= min{ f(u,w_1),f(w_1,w_2),...,f(w_r,v) }

(فکر کنم منظورش v بوده ولی توی صورت سوال نوشته بود w)

حل: برای جدا کردن راس u و v باید هیچ مسیری بین آنها نباشد، یعنی باید مسیر بالا هم نباشد، یعنی باید حداقل یک یال از آن حذف شود. پس هزینه ی برش از هزینه ی یال با وزن مینیمم در این مسیر بیشتر مساوی است. (به دلیل وجود مسیرهای دیگر مساوی نیست و بیشتر است.)

4- فرض کنید T درختی باشد که روی مجموعه رئوس V ساخته شده و روی یالها آن تابع وزن W' وجود دارد. می گوییم T یک درخت معادل شارش! (flow equivalent tree) است اگر در شرط اول از دو شرط درخت گومری-هو صدق کند؛ یعنی برای هر زوج رئوس u,v عضو V وزن برش u-v کمینه در G برابر وزن آن در T باشد. فرض کنید K گراف کامل روی V باشد. وزن هر یال K را f(u,v) تعریف کنید (وزن برش کمینه u-v). نشان دهید هر درخت پوشای با بیشترین وزن روی K یک درخت معادل شارش برای G است.

راهنمایی: برای هر u,v عضو V، قرار دهید u,w1,..,wr,v مسیر یکتا از u به v در T باشد. طبق 4.1 و این حقیقت که چون T یک درخت پوشای با ماکسیمم وزن است داریم:

f(u,v) <= min{ f(u,w1),..,f(wr,v)}

(4.1 = قسمت آخر سوال قبل!)

حل:

برای روشن شدن صورت سوال، مثلا گراف سه راسی را در نظر بگیرید که یالهاش این وزن ها را دارند:

G

(1,2): 1

(1,3): 2

(2,3): 4

----------

K

(1,2): 1

(1,3): 2

(2,3): 3

---------

T

(1,3): 2

(2,3): 3

برش کمینه بین 1 و 2 وزن 3 دارد.

وقتی یک درخت پوشا می سازیم، یعنی همه ی راسها به هم مسیر دارند و وقتی یک برش داریم می خواهیم هیچ دو راسی به هم مسیر نداشته باشند. پس باید بتوانیم همه ی آنها را جدا کنیم که این یعنی ماکسیمم بین برشهای مینیمم = ماکسیمم بین یالهای مسیرهای بین دو راس = یال درخت پوشای بیشینه.

به صورت ریاضی؛ باید نامساوی را برای همه ی مسیرهای ممکن بنویسیم و برای اینکه در همه صدق کند باید ماکسیمم مقادیر سمت چپ را بگیریم که همان وزن یال درخت پوشای بیشینه است.

5- فرض کنید (A, A') یک برش s-t مینیمم باشد که s در A است. x و y را هر دو راسی از A فرض کنید. گراف G' را با تبدیل همه ی راسهای A' به یک راس به نام v_A' بسازید. وزن هر یال (a,v_A') به اندازه ی مجموع وزن یالهای (a,b) است که b در A' است. بدیهی است که هر برشی در G' یک برش در G تعریف می کند. نشان دهید که یک برش x-y مینیمم در G' یک برش x-y مینیمم در G تعریف می کند.

حل:

همه ی راسهای A' به راس t وصل اند، پس برای اینکه x و y را (که در A هستند) از هم جدا کنیم، باید هیچ یالی بین راسهای x و y و مجموعه A' نباشد. چون این یالها مینیمم یالهایی هستند که باید قطع شوند (یک برش s-t بوده است) پس در برش مینیمم بین x و y هم همین یالها از مسیر بین x و y با t باید حذف شوند. پس می توانیم همه ی راسهای A' را به صورت یک ابرراس بگیریم و وزن یالها را هم جمع کنیم.

6- الگوریتم درخت گومری-هو: {پیشنهاد می کنم اول شکل پایین رو ببینید!}

افرازی از رئوس به مجموعه های S1,..,St انجام می دهیم و یک MST روی آنها می سازیم. w' تابعی است که وزن یالهای این درخت را می دهد. درخت ساخته شده T در ویژگی زیر صدق می کند:

ویژگی: به ازای هر یال (Si,Sj) از T، راسهای a و b به ترتیب در Si و Sj وجود دارند که w'(Si,Sj) = f(a,b) باشد (یعنی وزن برش کمینه a-b) و برش تعریف شده توسط یال (Si,Sj) یک برش a-b کمینه در G باشد.

الگوریتم از یک افراز بدیهی از V شروع می کند و n-1 تکرار انجام می دهد. در هر تکرار مجموعه Si در افراز را پیدا می کند که |Si|>2 باشد و افراز را با تقسیم Si و پیدا کردن یک درخت روی افرازی که در ویژگی صدق می کند، تصحیح می کند. به این صورت که x و y را دو راس متمایز Si قرار می دهد. ریشه درخت فعلی را در Si قرار می دهد و زیر درخت های با ریشه های فرزندان Si را در نظر می گیرد. هر زیر درخت به صورت یک ابرراس در می آید و گراف G' به این صورت به دست می آید. (راسهای Si در G' هستند و برای بقیه این ابرراسها ساخته می شوند نه خود Si). یک برش x-y مینیمم در G' پیدا می کنیم. فرض کنید (A,B) افرازی از راسهای G' باشد که این برش را تعریف می کنند که x در A و y در B باشد و w_xy را وزن این برش تعریف می کنیم. اشتراک S_i با A و B را به دست می آوریم و Si_x و Si_y می نامیم.

الگوریتم تقسیم ها و درخت را به روز می کند: افراز را با جایگزین کردن Si با Si_x و Si_y و درخت جدید بین راسهای Si_x و Si_y یال به وزن w_xy دارد. زیر درخت مجاور Si در درخت قبلی را در نظر بگیرید. بدون از دست رفتن عمومیت مساله فرض کنید گره متناظر این زیردرخت در A باشد. در این صورت زیردرخت با یک یال به Si_x وصل است. وزن این یال همان وزن اتصال زیردرخت به Si است. همه ی یالهای این زیردرخت وزنشان را حفظ می کنند.

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

مثال: برای درخت زیر اجرای الگوریتم به دست آوردن درخت گومری-هو نشان داده شده است.

حل:

چیزی که سوال می خواهد ثابت کنیم این است که برش کمینه در Si برای دو راس در Si با برش کمینه در گراف مساوی است. پس وقتی Si ها تک عضوی بشوند الگوریتم تمام می شود و همان درخت گومری-هو به دست می آید.

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

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

7- ثابت کنید اگر درخت گومری-هو برای یک گراف وزندار بدون جهت n-1 وزن متمایز داشته باشد آنگاه گراف فقط یک برش با کمترین وزن دارد.

حل:

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

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

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

تمرین با جواب

http://www.math.mcgill.ca/~vetta/CS692.dir/homework.html

http://www.public.asu.edu/~ccolbou/src/cse552f13.html

https://www.mpi-inf.mpg.de/departments/d1/teaching/ws13/Approx

http://www.cs.cornell.edu/courses/cs783/2003fa

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

4- نسخه ای از فروشنده دوره گرد متریک را در نظر بگیرید که در آن هدف پیدا کردن مسیر ساده شامل همه ی راسهای گراف است. سه مساله مختلف بر حسب تعداد سرهای مسیر که داده شده اند (0، 1، 2) وجود دارد. الگوریتم های تقریبی زیر را به دست آورید:

- اگر 0 یا 1 سر داده شده، الگوریتم با ضریب تقریب 3/2 بدهید.

- اگر هر دو سر مشخص شده اند، الگوریتم با ضریب 5/3 بدهید.

راهنمایی: از ایده الگوریتم 3.10 استفاده کنید. (الگوریتم 3.10 فروشنده دوره گرد متریک با ضریب 3/2 است که فقط راسهای درجه فرد را اصلاح می کرد.)

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

الف)

همان الگوریتم 3.10 را اجرا می کنیم، فقط به جای اینکه در آخر یک دور بسازیم، یک مسیر می سازیم:

در حالت 1 سر داده شده: یال ورودی به راس داده شده را حذف می کنیم.

در حالت 0 سر داده شده: یال با بیشترین وزن در دور را حذف می کنیم.

اثبات: یک تطابق کامل با کمترین وزن هزینه ای کمتر از نصف هزینه ی مسیر گذرنده از تمام رئوس دارد: چون اگر یالهای مسیر را یکی در میان حذف کنیم یک تطابق کامل می شود.

هزینه ی درخت هم از هزینه ی جواب بهینه کمتر است. پس کل هزینه از 3/2 جواب بهینه کمتر است. پس ضریب تقریب الگوریتم 3/2 است.

ب)

همان الگوریتم 3.10 را اجرا می کنیم، فقط به جای گراف اویلری، گراف نیمه اویلری می سازیم که درجه ی دو راس داده شده در آن فرد باشد. برای این کار می توانیم اگر درجه آنها فرد بود آن را تغییر ندهیم، در غیر این صورت در تطابقمان این راسها را هم در نظر بگیریم. در حالت اول جوابی که به دست می آید 3/2 جواب بهینه است. در حالت دوم جوابی که به دست می آید از هزینه MST +  دو سوم هزینه مسیر TSP کمتر است.

5- فرض کنید گراف کامل بدون جهت داده شده که طول یالهای آن 1 یا 2 است (بدیهی است که در نامساوی مثلث صدق می کند). یک الگوریتم با ضریب تقریب 4/3 برای فروشنده دوره گرد در این گرافها بدهید.

راهنمایی: از پیدا کردن 2-تطابق مینیمم شروع کنید. یک 2-تطابق زیرمجموعه ای از یالهاست که هر راس دقیقا دو یال مجاور دارد.

حل: یک تطابق کامل مینیمم پیدا می کنیم و یالهای آن را حذف می کنیم، بعد یک تطابق کامل مینیمم دیگر پیدا می کنیم و یالهای این تطابق و تطابق قبلی را به عنوان 2-تطابق مینیمم در نظر می گیریم.

به MST در راسهایی که درجه فرد دارند از 2-تطابق کمینه یال اضافه می کنیم. می دانیم هزینه ی جواب بهینه از هزینه ی یالهای 2-تطابق کمینه بیشتر است. وزن 2-تطابق کمینه از وزن جواب بهینه مساله کمتر مساوی است. (چون در جواب بهینه یک دور داریم اما اینجا یک یا چند دور داریم.)

نمونه گیری تصادفی و رند کردن تصادفی LPها (فصل 5 WS)

تضمین عملکرد الگوریتم تقریبی که انتخاب تصادفی می کند، امیدریاضی (expected value) جواب به دست آمده نسبت به {بر حسب} جواب بهینه است، وقتی روی همه ی انتخاب های تصادفی حساب شود.

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

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

همچنین گاهی می توانیم با احتمال بالا تضمین عملکرد الگوریتم تقریبی تصادفی را بدهیم. یعنی احتمال اینکه تضمین عملکرد نادرست باشد یک بر چندجمله ای بر حسب اندازه ورودی است. معمولا می توانیم این چندجمله ای را هرقدر می خواهیم بزرگ کنیم (و در نتیجه هر چقدر می خواهیم احتمال را کم کنیم) که تضمین عملکرد را با یک ضریب ثابت بدتر می کند. اینجا غیرتصادفی کردن کمتر لازم است، هر چند گاهی با روشهای پیچیده تری امکان پذیر است.
دو الگوریتم تصادفی برای مسائل maximum satisfiability و maximum cut می دهیم. نشان می دهیم که جوابی که به صورت تصادفی یکنواخت از مجموعه جوابها انتخاب شده باشد، یک الگوریتم تقریبی تصادفی خوب می دهد. برای مساله تصدیق بیشینه می توانیم از این هم جلوتر برویم و نشان دهیم انتخاب غیریکنواخت (بایاس شده) به تضمین عملکرد بهتری می رسد.

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

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

یک الگوریتم ساده برای تصدیق بیشینه (MAX SAT) و برش بیشینه (MAX CUT)

برای هر کدام از این دو مساله یک الگوریتم تصادفی 1/2-تقریبی می دهیم.

در مساله MAX SAT، ورودی شامل n متغیر x_1 و ... و x_n است که true یا false هستند؛ m عبارت C_1 و ... و C_m که یای منطقی متغیرها و نقیض آنها هستند؛ وزن های نامنفی w_j برای C_j. هدف مساله پیدا کردن تخصیصی از true/false به x_i ها است که وزن عبارتهای صادق را بیشینه کند. یک عبارت صادق است، اگر یکی از متغیرهای نقیض نشده ی آن true شود، یا یکی از متغیرهای نقیض شده آن false شود.

تعاریف:

literal: به x_i و نقیض آن x'_i می گویند.

positive literal: خود x_i

negative literal: نقیض متغیر = x'_i

اندازه یا طول: تعداد literal های یک عبارت: L_j برای C_j

عبارت یکه: عبارت با طول 1

بدون از دست رفتن عمومیت مساله فرض کنید هیچ literal ای در یک عبارت تکرار نشده باشد. فرض کنید هر دوی x_i و x'_i هم در یک عبارت نباشند. فرض کنید عبارتها متمایز هستند (چون اگر مشابه باشند یکی از آنها را نگه می داریم و وزن مجموع آنها را به آن اختصاص می دهیم.).

الگوریتم تصادفی:

با احتمال 1/2 هر متغیر x_i را true می گذاریم. دید دیگر به این حل برای مساله انتخاب تصادفی یکنواخت مقادیر متغیرها از بین همه ی حالتها است. این الگوریتم تقریب خوبی از مساله به ما می دهد.

قضیه: ثابت کنید ضریب تقریب الگوریتم بالا 1/2 است.

اثبات: متناظر هر عبارت یک متغیر Y_j در نظر بگیرید که اگر آن عبارت صادق باشد 1 و در غیر این صورت 0 باشد. در این صورت مجموع وزن عبارتهای صادق به صورت زیر است:

w = sum_j_1_m (Y_j*w_j)

فرض کنید OPT جواب بهینه برای این نمونه از مساله MAX SAT باشد. طبق خطی بودن امید ریاضی داریم:

E(w) = sum_j_1_m (w_j*E(Y_j)) = sum_j_1_m (w_j*pr(C_j=true))

برای هر عبارت C_j که j =1...m، احتمال صادق نبودن آن احتمال این است که هیچ کدام از متغیرهای درون آن درست نباشند (نقیض آنها نادرست). پس چون احتمال درست/نادرست بودن 1/2 است:

pr(C_j = true) = (1-1/2^L_j) >= 1/2

که این نامساوی به دلیل L_j >=1 بودن درست است. پس:

E(w) <= sum_j_1_m(w_j*1/2) = 1/2 sum_j_1_m(w_j) >= 1/2 OPT

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

(پایان اثبات)

دقت کنید که اگر L_j >= k باشد (برای همه عبارتها)، آنگاه الگوریتم ما 

1-1/2^k

تقریبی است. پس عملکرد آن روی MAS SAT ای که عبارتهای طولانی داشته باشد بهتر است.

مثال tight: حالتی که L_j = 3 باشد را MAX E3SAT می نامند. تقریب آن با این روش 7/8 به دست می آید که در صورتی که P=NP نباشد جواب بهتری برای آن نیست.

(اثبات: فصل 16.3 کتاب!)

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

در مساله برش بیشینه ورودی یک گراف بدون جهت است که یالهای وزندار نامنفی دارد. هدف افراز راسها به دو مجموعه U و V است که وزن یالهای بین این دو قسمت ماکسیمم شود که به آن برش می گوییم. در حالتی که وزن یالها 1 باشد، به آن مساله برش بیشینه بدون وزن می گویند.

الگوریتم با ضریب تقریب 1/2 و تصادفی:

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

اثبات ضریب تقریب: متغیر X_ij را 1 بگیرید اگر یال (i,j) در برش بود و 0 در غیر این صورت. Z را متغیر تصادفی بگیرید که جمع وزن یالهای برش است. پس:

Z = sum_(i,j) (w_ij*X_ij)

E(Z) = sum_(i_j) (w_ij*E(X_ij)) = sum_(i,j) (w_ij*pr( (i,j) in cut) )

OPT را هم جواب بهینه این مساله بگیرید. (برای این ورودی).

احتمال حضور یال (i,j) در برش به اندازه ی احتمال حضور هر سر آن در هر کدام از این مجموعه هاست که 2/4=1/2 است، پس:

E(Z) = 1/2 sum_(i,j) (w_ij) >= 1/2 OPT

چون وزنها نامنفی هستند، جواب بهینه کمتر مساوی جمع وزن ها است.

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

غیر تصادفی کردن

هدف: به دست آوردن الگوریتم قطعی با جوابی به خوبی امیدریاضی جواب الگوریتم تصادفی

برای مساله تصدیق بیشینه (MAX SAT)، به جای انتخاب تصادفی مقدار درست یا نادرست برای متغیر، یک روش دیگر به کار می بریم که همان مقدار امیدریاضی آن را بدهد. مقادیر متغیرهای یکی بعد از دیگری تعیین می شود.

اول فرض کنید ما فقط مقدار x_1 را قطعی تعیین می کنیم و بقیه با همان احتمال 1/2 تعیین می شوند. پس بهترین راه مقداردهی آن این است که امیدریاضی جواب را بیشینه کنیم. یعنی امیدریاضی w (وزن عبارتهای درست) را به شرط درست بودن x_1 و امیدریاضی w را به شرط نادرست بودن x_1 به دست بیاوریم و هر کدام مقدار x_1 را بیشتر کرد، آن را به عنوان مقدار x_1 در نظر می گیریم. این از نظر شهودی منطقی است، چون ماکسیمم از میانگین بیشتر است و امید ریاضی W میانگین آن روی دو مقدار ممکن x_1 است. در این حالت، یک نسخه ی الگوریتمی از امید ریاضی که حداقل نصف بهینه است به دست می آوریم که تعداد متغیرهای تصادفی را کمتر می کند.

به صورت ریاضی:

if E(W|x_1=true) >= E(W|x_1=false) ==> x_1 = true, else x_1 = false

(conditional probability) ==>

E(W) = E(W|x_1=true)Pr(x_1=true)+E(W|x_1=false)Pr(x_1=false) = 1/2 (E(W|x_1=true)+E(W|x_1=false)

b1=arg max( E(W|x_1=b1) ) ==> E(W|x_1=b1) > E(W)

یعنی انتخاب قطعی مقدار x_1 تضمین مقداری بزرگتر مساوی امیدریاضی الگوریتم کاملا تصادفی می دهد.

با استقرا برای حالتی که مقدار متغیرهای قبلی مشخص شده باشد برای متغیر x_i به همین صورت مقدار انتخاب می کنیم. بعد از تعیین آخرین متغیر، وزن به دست آمده از الگوریتم ما بیشتر مساوی مقدار به دست آمده از الگوریتم تصادفی است که آن هم از نصف بهینه بیشتر است. پس الگوریتم 1/2-تقریبی است.

برای اینکه بتوانیم این الگوریتم را اجرا کنیم باید بتوانیم این احتمالهای شرطی را محاسبه کنیم.

(پایان اثبات)

تکنیک غیرتصادفی کردن برای انواع زیادی از الگوریتم های تصادفی کار می کند که در آنها متغیرها به صورت مستقل مقداردهی می شوند و احتمالات شرطی در زمان چندجمله ای قابل محاسبه هستند. این کار گاهی روش امیدریاضی شرطی (method of conditional expectation) هم نامیده می شود، چون از امید ریاضی شرطی استفاده می کند. برای برش بیشینه هم با استدلالی دقیقا مثل سوال قبل می توان به نسخه ی غیرتصادفی 1/2-تقریبی برای آن رسید.

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

پرتاب سکه نامتقارن

چطور می توانیم الگوریتم تصادفی تصدیق بیشینه (MAX SAT) را بهبود دهیم؟ نشان می دهیم که با نامتقارن کردن احتمال مقادیر x_i یعنی با احتمالی به غیر از 1/2 می توانیم آن را بهبود دهیم. برای این کار ساده تر است MAX SAT هایی را در نظر بگیریم که هیچ عبارت یکه (با یک متغیر) x'_i ندارند، یعنی هیچ پرانتری ندارند که درون آن فقط نقیض یک متغیر باشد). بعدا نشان می دهیم که می توانیم این فرض را حذف کنیم. فرض کنید مقدار x_i را با احتمال p>1/2 درست (true) بگذاریم. مشابه قبل باید احتمال صادق بودن هر عبارت را به دست بیاوریم.

لم: با فرض درست بودن مقدار x_i با احتمال p>1/2 به صورت مستقل، احتمال اینکه هر عبارتی صادق باشد حداقل به اندازه ی مینیمم p و 1-p^2 است.

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

1-p^a*(1-p)^b

که در آن a تعداد متغیرهای نقیض شده و b تعداد متغیرهای معمولی در این عبارت است که a+b=L_j>=2 است. داریم:

1-p < 1/2 < p ==> pr( clause = true ) >= 1-p^(a+b) = 1-p^L_j >= 1-p^2

(پایان اثبات).

بهترین تضمین جواب را وقتی به دست می آوریم که p=1-p^2 باشد که نتیجه می دهد: p=1/2(sqrt(5)-1)=0.618

از این لم قضیه زیر نتیجه می شود:

قضیه: با کاری که گفته شد به الگوریتم تصادفی min(p,1-p^2)-تقریبی می رسیم، برای مساله تصدیق بیشینه که پرانتر فقط دارای یک متغیر نقیض شده نداشته باشد.

اثبات:

E(W) = sum_j_1_m (w_j*Pr(C_j=true) ) >= min(p,1-p^2)*sum_j_1_m( w_j ) >= min(p,1-p^2)*OPT

(پایان اثبات).

می خواهیم این را به تصدیق بیشینه تعمیم بدهیم، پس از کرانی بهتر از جمع وزن عبارتها استفاده می کنیم. فرض کنید برای هر i وزن عبارت فقط شامل این متغیر حداقل به اندازه وزن عبارت شامل فقط نقیض آن باشد؛ این بدون از دست رفتن عمومیت مساله برقرار است، چون در غیر این صورت تغییر متغیر می دهیم و نقیض آن را به عنوان متغیر می گیریم. v_i را وزن پرانتز شامل فقط نقیض x_i بگیرید و اگر وجود نداشت آن را 0 بگذارید.

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

اثبات:

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

قضیه: می توانیم الگوریتم تقریبی تصادفی با ضریب 1/2(sqrt(5)-1) به دست بیاوریم. (برای مساله تصدیق بیشینه).

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

این الگوریتم می تواند با روشی که گفته شد غیرتصادفی شود.

چند برش و k-برش (فصل 4 وزیرانی)

الگوریتم های تقریبی برای تعمیم هایی از مساله برش کمینه بررسی می شوند که np-hard هستند.

یک گراف بدون جهت همبند با یالهای وزندار داریم، یک برش با کمک افراز مجموعه رئوس به دو زیرمجموعه، مجموعه ی همه ی یالهایی است که هیچ دو سر آن در یک مجموعه نیستند (یعنی هر سر آن در یکی از مجموعه ها است). بدیهی است حذف برش از گراف آن را ناهمبند می کند.

ترمینالهای s و t را از مجموعه رئوس در نظر بگیرید: افرازی از رئوس را در نظر بگیرید که s در یک مجموعه و t در مجموعه دیگر باشد. برشی که با این افراز تعریف شود یک برش s-t نامیده می شود. مساله پیدا کردن برش با کمترین وزن و برش s-t با کمترین وزن به کمک الگوریتم شارش بیشینه به صورت کارا قابل حل هستند. این دو مساله را تعمیم می دهیم:

مساله چند برش: یک مجموعه ترمینال {S={s_1,...,s_k از رئوس داده شده، یک چند برش مجموعه ای از یالهاست که حذف آنها این ترمینالها را از هم ناهمبند می کند. مساله چندبرش مجموعه یال با کمترین وزن را می خواهد.

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

در این فصل الگوریتم های با ضریب زیر برای این دو مساله ارائه می دهیم:

2-2/k

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

مساله چند برش

یک برش ایزوله برای s_i را مجموعه ای از یالها تعریف می کنیم که حذف آنها s_i را از بقیه ترمینالها جدا می کند.

الگوریتم:

1- برای هر i از 1 تا k، برش ایزوله برای s_i با کمترین وزن را حساب کن (C_i).

2- از بین این برشها سنگین ترین آنها را حذف کن و اجتماع بقیه را برگردان (C).

--------

هر محاسبه در مرحله 1 با تشخیص ترمینالهای S-{s_i} به شکل یک گره و پیدا کردن برش مینیمم با محاسبه ی شارش بیشینه از s_i به گره اجتماع بقیه ترمینالها انجام می شود. بدیهی است حذف C از گراف هر زوج ترمینالی را ناهمبند می کند، پس یک چند برش است. (چون در الگوریتم همه ی راسها به جز یکی را از بقیه جدا کردیم و آن آخری هم چون بقیه از آن جدا هستند از بقیه جداست.)

قضیه: الگوریتم بالا ضریب تقریب زیر را دارد:

2-2/k

اثبات: فرض کنید A چندبرش بهینه باشد. می توانیم A را به صورت اجتماع k تا برش ببینیم: حذف A از گراف k مولفه همبندی ایجاد می کند که هر کدام یک ترمینال دارند (چون A چند برش با کمترین هزینه است، بیش از k مولفه ساخته نمی شود). قرار دهید A_i را به عنوان برشی که مولفه شامل s_i را از بقیه گراف جدا می کند. پس اجتماع A_i ها A می شود.

چون هر یال A مجاور دو مولفه است، هر یال در دو برش A_i ظاهر می شود. پس جمع وزن یالهای A_i ها دو برابر جمع وزن یالهای A است.

بدیهی است A_i یک برش ایزوله برای s_i است. چون C_i یک برش ایزوله با کمترین وزن برای s_i است، پس وزن C_i از وزن A_i کمتر مساوی است. (در الگوریتم این طوری حساب کردیم). توجه کنید که این الگورتیم تا همین جا با گرفتن اجتماع k برش C_i یک الگوریتم تقریبی با ضریب 2 است. در آخر چون C با حذف سنگین ترین برش C_i به دست آمده است، داریم:

w(C) <= (1-1/k) sum_1_k w(C_i) <= (1-1/k) sum_1_k (w(A_i)) = 2(1-1/k)w(A)

(نامساوی اول را می توان از اینجا به دست آورد که میانگین یک سری عدد از ماکسیمم آنها کمتر است). پایان اثبات.

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

مثال: یک مثال tight برای این الگوریتم: گراف با 2k راس شامل یک دور k راسی و ترمینالهای متمایز متصل شده به هر راس آن. یالهای دور وزن 1 دارند و یالهای متصل به ترمینالها وزن 2-epsilon دارند.

برای هر ترمینال s_i، برش ایزوله با کمترین وزن برای s_i، یال متصل به s_i است. پس جواب الگوریتم (C) وزن (k-1)(2-epsilon) دارد. از طرف دیگر جواب بهینه حذف یالهای دور است که وزن k دارند.

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

مساله k-برش مینیمم

یک الگوریتم معمولی برای k-برش این است: یک برش مینیمم در هر مولفه همبندی حساب کن و کم وزن ترین آنها را حذف کن و این کار را ادامه بده تا k مولفه همبندی بماند. این الگورتیم به ضریب 

2-2/k

می رسد، اما اثبات آن سخت است. به جای این الگوریتم ساده تری با همین زمان می دهیم: بازنمایی برشهای کمینه با درخت گومری-هو ( :)) )

برشهای کمینه هم مثل برشهای تقریبا بهینه؟ (sub-optimal) در گرافهای بدون جهت ویژگی های ساختاری جالبی دارند، بر خلاف برش در گرافهای جهت دار. وجود درختهای گومری-هو یکی از نتایج این مشخصات است.

فرض کنید T درختی باشد که روی مجموعه رئوس V ساخته شده؛ یالهای T لازم نیست از E باشند. فرض کنید e یک یال درخت T باشد. حذف آن از درخت دو مولفه همبندی ایجاد می کند. فرض کنید S و S' مجموعه رئوس این مولفه ها باشند. برش در گراف G به صورت افراز (S,S') را برش متناظر یال e تعریف می کنیم. تابع وزن w' را روی یالهای T تعریف کنید. درخت T یک درخت گومری-هو است اگر:

1- برای هر زوج راسهای u و v از V، وزن برش u-v کمینه برابر متناظر آن در T باشد.

2- برای هر یال e از T، وزن w'(e) وزن برش متناظر e در گراف اصلی باشد.

بدیهی است که یک برش u-v مینیمم در T همان کم وزن ترین یال در مسیر بین u و v است (فرض کنید e) و برش متناظر e در G باید u و v را جدا کند.

به صورت شهودی، پیدا کردن یک k-برش کم وزن نیازمند برداشتن برشهای کم وزن است که مولفه های زیادی ایجاد می کنند. توجه کنید که n-1 برش متناظر یالهای T شامل برشهای u-v مینیمم برای هر زوج راس از مجموعه رئوس هستند. (C(n,2)). این حقیقت و لم بعد با هم استفاده از درخت گومری-هو برای پیدا کردن یک k-برش کم وزن را اثبات می کنند.

لم: S را اجتماع برشهای گراف متناظر با L یال T در نظر بگیرید. آنگاه حذف S از گراف یک گراف با حداقل L+1 مولفه ایجاد می کند.

اثبات: حذف L یال مذکور از درخت دقیقا L+1 مولفه می سازد، آنها را V_1 و ... و V_(L+1) بنامید. بدیهی است حذف S از G زوجهای V_i و V_j را ناهمبند می کند. بنابراین ما باید حداقل L+1 مولفه همبندی به دست بیاوریم.

در نتیجه ی لم قبل، اجتماع k-1 برش برداشته شده از T یک k-برش در گراف می سازد. الگوریتم کامل به صورت زیر است:

الگوریتم k-برش:

1- یک درخت گومری-هو T برای گراف G بسازید.

2- اجتماع کم وزن ترین k-1 برش از n-1 برش متناظر یالهای T در گراف را به عنوان خروجی برگردانید. (C)

--------

طبق لم قبل حذف C از G حداقل k مولفه همبندی می سازد. اگر بیش از k مولفه ساخته شد، بعضی از یالهای حذف شده را دوباره برگردانید تا دقیقا k مولفه شود.

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

2-2/k

دارد.

اثبات: فرض کنید A جواب k-برش بهینه گراف باشد. همان طور که در قضیه 4.4 گفته شد، می توانیم A را به صورت اجتماع k برش ببینیم: V_1 و ...و V_k را k مولفه همبندی شکل گرفته با حذف A از G بگیرید و A_i را برشی که V_i را از بقیه جدا می کند. پس A=A_1 U ...UA_k و در نتیجه هر یال A در دو تا از این برشها می افتد.

sum_i_1_k( w(A_i) ) = 2*w(A)

بدون از دست رفتن کلیت مساله فرض کنید A_k سنگین وزن ترین این برشها باشد. ایده ی بقیه اثبات نشان دادن این است که k-1 برش متناظر یالهای T هستند که وزنشان کمتر از وزن برشهای A_1 ,..., A_(k-1) هستند. پس چون الگوریتم k-1 برش سبکتر تعریف شده توسط T را بر می دارد، قضیه درست است.

k-1 برش به صورت زیر مشخص می شوند. B را مجموعه یالهای T بگیرید که V_1 و ... و V_k را متصل می کنند. گراف با رئوس V و یالهای B را در نظر بگیرید و هر یک از مجموعه های V_i را به صورت یک ابرراس در نظر بگیرید. گراف حاصل باید همبند باشد (چون T همبند بوده است).. یالها را تا زمانی که یک درخت باقی بماند حذف کنید. B' زیر مجموعه B را مجموعه یالهای باقیمانده در نظر بگیرید. |B'|=k-1 . یالهای B' برشها (k-1 تا)ی مورد نظر ما را مشخص می کنند.

بعد ریشه درخت را V_k بگذارید (سنگین ترین برش در بین A_iها). این کار به پیدا کردن ارتباط بین یالهای B' و مجموعه های V_1,...,V_(k-1) کمک می کند: هر یال متناظر مجموعه ای است که از آن بیرون می آید. (در درخت ریشه دار).

فرض کنید یال (u,v) از B' متناظر مجموعه V_i باشد. وزن برش u-v مینیمم در گراف، w'(u,v) است. چون A_i یک برش u-v در گراف است:

w(A_i) >= w'(u,v)

پس وزن هر برش بین A_1 و ... و A_(k-1) حداقل به اندازه ی برش تعریف شده در گراف متناظر یال B' است. از این موضوع و این حقیقت که C اجتماع k-1 سبکترین برش تعریف شده توسط T است به دست می آید:

w(C) <= sum_B' (w'(e)) <= sum_i_1_k-1 w(A_i) <= (1-1/k) sum_i_1_k (w(A_i)) = 2(1-1/k)w(A)

مثال tight: برای الگوریتم چندبرش بالا با 2k راس برای این مساله هم مثال خوبی است. (البته نیازی به علامت گذاری راسها به عنوان ترمینال نداریم). در زیر مثالی برای k=4 با درخت گومری-هو متناظر آن می دهیم.

سبکترین k-1 برش در درخت گومری-هو وزن 2-epsilon دارند که متناظر برداشتن یالهای با وزن 2-epsilon از G است. پس k-برش برگردانده شده توسط الگوریتم وزن (k-1)(2-epsilon) دارند. از طرف دیگر جواب بهینه برداشتن یالهای با وزن 1 است که در مجموع k می شود.

ادامه سوالات فصل 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 عضو است: خود رشته و معکوس آن.

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

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

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

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

(؟)

دوگان LP

دقت کنید که ضریبهای a و b و c در هر دو LP مقدارهای مشخص هستند.

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

5- یک تطابق ماکسیمال را می توان با یک الگوریتم حریصانه به دست آورد: یک یال را بردارید و دو سر آن را حذف کنید، این کار را ادامه بدهید تا هیچ یالی باقی نماند. آیا این کار باعث می شود الگوریتم 1.2 حریصانه شود؟

(الگوریتم 1.2: پوشش راسی با  بیشترین اعضا: یک تطابق ماکسیمال در گراف پیدا کنید و راسهای تطابق یافته را به عنوان خروجی اعلام کنید.)

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

6- یک کران پایین برای مساله پوشش راسی با هزینه دلخواه بدهید.

راهنمایی: اگر از دوگان LP استفاده نکنید ساده نیست.

پوشش راسی را با LP بخواهیم بیان کنیم متغیرهای آن را راسها می گیریم که 0 یعنی در پوشش راسی نیست و 1 یعنی هست. قیود ما یالها هستند که جمع دو متغیر راس هستند که باید از 1 کمتر باشند. تابع هدف ما هم مینیمم کردن جمع متغیرها است.

IP --> LP:

minimize sum(cost(i)*xi)

s.t. xi+xj <= 1 (i,j) in E

xi in {0,1} --> xi >= 0, xi <= 1

LP:

minimize sum(cost(i)*xi)

s.t. -xi-xj >= -1

-xi >= -1

xi >= 0

dual LP:

maximize sum_i_E(-yi)+sum_j_1_n(-yj)

s.t. yi <= cost(i)

yi >= 0

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

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

7- فرض کنید A={a1,...,an} مجموعه متناهی باشد که رابطه ای بازتابی، نامتقارن و ترایا روی آن تعریف شده است. این رابطه یک ترتیب جزئی روی A نام دارد. دو عضو ai و aj از A را قابل مقایسه می گویند اگر ai R aj باشد یا aj R ai باشد. دو عضو غیرقابل مقایسه به دو عضوی می گویند که قابل مقایسه نباشند. یک زیر مجموعه S از A را زنجیره می نامند اگر اعضای آن دو به دو قابل مقایسه باشند. اگر اعضای S دو به دو غیرقابل مقایسه باشند به آن ضدزنجیره می گویند. یک پوشش زنجیره (ضد زنجیره) مجموعه ای از زنجیره ها (ضد زنجیره ها) است که دو به دو مجزا هستند و A را پوشش می دهند. اندازه این پوشش تعداد زنجیره ها (ضد زنجیره ها)ی آن است. ثابت کنید نتیجه min-max زیر درست است: اندازه طولانی ترین زنجیره به اندازه کوچکترین پوشش ضدزنجیره است.

راهنمایی: اندازه طولانی ترین زنجیره را m فرض کنید. برای هر a عضو A، تابع f(a) را اندازه طولانی ترین زنجیره که در آن a کمترین عضو است قرار دهید. حالا افراز A را به مجموعه های A_i در نظر بگیرید که اعضای آنها زنجیره های به طول i از اعضای A هستند. i بین 1و m.

حل:

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

8- ثابت کنید در هر ترتیب جزئی، اندازه ی بزرگترین ضدزنجیره مساوی کوتاهترین پوشش زنجیره ای است.

راهنمایی: از قضیه ... استفاده کنید. یک ترتیب جزئی روی یک مجموعه n عضوی داده شده است، گراف دوبخشی U و V و E را در نظر بگیرید که |U|=|V|=n و اگر و تنها اگر a_i <a_j باشد یال (u_i,v_j) عضو E است.

حل:

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

*بقیه سوالات فصل مربوط به ضمیمه بودند.