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

1- در مساله k-برش ماکسیمم، گراف بدون جهت G با وزنهای نامنفی wij>=0 به ازای هر یال (i,j) گراف داده شده است. هدف افراز راسهای گراف به k قسمت V1,...,Vk است طوری که وزن یالهایی که سرهای مختلف آن در مولفه های همبندی مختلف است ماکسیمم شود.

یک الگوریتم (k-1)/k تقریبی برای MAX k-Cut بدهید.

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

میانگین وزن k-1 برش سنگینتر از میانگین وزن k برش سنگینتر بیشتر است، پس ضریب تقریب (k-1)/k است.

2-الگوریتم حریصانه زیر را برای مساله برش ماکسیمم در نظر بگیرید. فرض کنید راسها از 1 تا n برچسب زده شده اند. در تکرار اول، الگوریتم راس 1 را در U قرار می دهد. در تکرار k-ام الگوریتم راس k را یا در U یا در W می گذاریم. برای اینکه تصمیم بگیریم کدامیک از انتخابها را انجام دهیم به مجموعه یالهای F که راس k یک سر آنها است و سر دیگر آنها بین راسهای 1,...,(k-1) است، پس F={(j,k)| 1<= j <= k-1}. ما بر اساس اینکه کدام انتخاب تعداد یالهای F را که بریده می شود بیشتر می کند، عمل می کنیم.

الف) ثابت کنید که این الگوریتم 1/2-تقریبی است. (برای مساله برش ماکسیمم)

ب) ثابت کنید که این الگوریتم معادل غیرتصادفی کردن الگوریتم بخش 5.1 با روش امیدریاضی شرطی است.

حل:

الف)

OPT <= sum(deg_U(v))+sum(deg_W(v)) <= 2*sum(max(deg_U(v),deg_W(v)))

ALG(v) = max(deg_U(v),deg_W(v)) ==> ALG = sum(max(deg_U(v),deg_W(v)))

==> OPT <= 2*ALG

(نکته اینه که سوال تکراریه..؟)

ب)

pr(k in U)=1/2 = pr(k in W)

E(#edges) = E(#edges| v_k in U)Pr(v_k in U)+E(#edges| v_k in W)pr(v_k in W)=1/2(E(#edges|v_k in U)+E(#edges|v_k in W) )

b_k = argmax( E(#edges|v_k in b_k) ) ==> E(#edges|v_k in b_k) >= E(#edges)

(j,k) in F: pr((j,k) in U| v_(k-1)=b_(k-1),...) = 1 if j in W, 1-(1/2)^k if j in U

3- در برش ماکسیمم جهت دار (MAX DICUT)، یک گراف جهتدار داده شده و هر یال آن وزن نامنفی دارد wij >= 0. هدف تقسیم راسها به دو زیرمجموعه U و W است که جمع وزن یالهایی که از U به W می روند ماکسیمم شود. یک الگوریتم تصادفی 1/4-تقریبی برای این مساله بدهید.

همان استدلال و روش سوال بالا+

E(#edges) >= 1/4 OPT

که 1/4 از ضرب احتمال حضور سر اول یال در U و سر دوم آن در W به دست آمده است: 1/2*1/2=1/4