کوتاهترین ابررشته - اصلاحیه

S: مجموعه رشته های ورودی

M: مجموعه شامل همه ی ابررشته های بهینه هر دو رشته (از اعضای S)

Set(x): مجموعه اعضای S که زیررشته ی x هستند. (=x ابررشته ی آنهاست)

هزینه ی Set(x) طول رشته x است یعنی |x|.

OPTs: جواب بهینه ی پوشش مجموعه ای که در آن اعضای مجموعه مرجع رشته ها و مجموعه ها Set(x) ها هستند که x اجتماع M و S است.

OPT: طول کوتاهترین ابررشته شامل همه ی رشته ها (جواب بهینه مساله)

الگوریتم:

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

فرض کنید رشته هایی که این الگوریتم برگرداند a_1,...,a_k باشند.

2- این رشته ها را با هر ترتیبی به هم بچسبانید. (دلخواه)

3- رشته ی حاصل را به عنوان جواب برگردانید.

تحلیل:

(چون هزینه ای که مینیمم می کند، طول رشته ها است احتمالا جواب خوبی به دست می آید.)

لم: OPT <OPTs <2.OPTs

(جواب بهینه ی مساله ی پوشش مجموعه ای جواب تقریبی برای این مساله با ضریب 2 است.)

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

اثبات نامساوی دوم: کافی است ثابت کنیم جواب الگوریتم پوششی با هزینه ی کمتر از 2 برابر جواب بهینه است. اولین مکانی که هر رشته ی S در جواب الگوریتم ما ظاهر می شود علامت بزنید. این مکان ها متمایزند چون هیچ رشته ای زیر مجموعه ی رشته ی دیگر نیست. (اگر دو رشته مکان شروع یکسان داشته باشند رشته ای که زودتر تمام می شود زیررشته ی رشته ی دیگر می شود). با استدلال مشابه پایان این رشته ها هم متمایز است. آنها را به این ترتیب شماره گذاری می کنیم. این لیست را روی رشته های a_i افراز می کنیم (جزء مساله). (اشتراک a_i ها کمتر از یک رشته در S است در غیر این صورت بهینه نمی شدند.). هزینه ی جواب الگوریتم ما جمع طول ابررشته های a_i است. بدیهی است که a_i و a_i+2 با هم اشتراک ندارند. پس هر رشته حداکثر در دو تا از ابررشته ها (a_i و a_i+1) آمده است پس هزینه کمتر از دو برابر جمع طول a_i ها است که آن هم از جواب بهینه بیشتر است.

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

1- سختی مساله درخت اشتاینر در مشخص کردن زیرمجموعه بهینه از راسهای اشتاینر است که باید در درخت باشند. نشان دهید که اگر این مجموعه داده شده باشد، مساله ی درخت اشتاینر به صورت بهینه در زمان چند جمله ای قابل محاسبه است.

راهنمایی: یک MST روی اجتماع این مجموعه و مجموعه رئوس "لازم" پیدا کنید.

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

2- گراف با یالهای وزندار نامنفی داده شده است. S مجموعه ی فرستنده ها و R مجموعه گیرنده ها دو زیرمجموعه مجزا از رئوس هستند. مساله پیدا کردن زیر گراف با کمترین هزینه است که هر گیرنده را به حداقل یک فرستنده وصل کند. نمونه ها را به دو مجموعه تقسیم کنیم: آنهایی که اجتماع این دو مجموعه تمام رئوس می شود و حالتی که نمی شود. نشان دهید این دو مساله به ترتیب در P و NP-hard هستند. برای حالت دوم الگوریتم تقریبی با ضریب 2 بدهید.

راهنمایی: یک راس جدید اضافه کنید که به هر فرستنده با یال با هزینه ی 0 وصل شده باشد. راس جدید و همه ی گیرنده ها را "لازم" و بقیه رئوس را اشتاینر در نظر بگیرید. درخت اشتاینر با کمترین هزینه را پیدا کنید.

حالتی که اجتماع این دو مجموعه کل رئوس شود: همه ی راسهای فرستنده را با هم ادغام می کنیم و یک ابر راس می سازیم. در این گراف MST را حساب می کنیم. چون هدف سوال وصل کردن این راسها با هزینه ی مینیمم است جواب بهینه MST است پس مساله در P است.

حالتی که اجتماع این مجموعه کل رئوس نشود: چون مجموعه ای از رئوس هستند که حضور آنها لازم نیست مساله به درخت اشتاینر تبدیل می شود که در NP-Hard است. برای حل آن راهنمایی سوال را اجرا می کنیم و الگوریتم با ضریب تقریب 2 به دست می آوریم.

3- کاهشی با حفظ ضریب تقریب از مساله پوشش مجموعه ای به مساله بعد بدهید و نشان دهید که این مساله نمی تواند ضریب تقریب بهتر از O(log n) داشته باشد.

درخت اشتاینر جهت دار: یک گراف جهت دار با یالهای با هزینه ی نامنفی داده شده است. مجموعه رئوس V به دو زیرمجموعه "لازم" و "اشتاینر" افراز شده است. یکی از راسهای لازم (r) یک راس ویژه است. مساله پیدا کردن درخت با کمترین هزینه است که ریشه ی آن r باشد و شامل همه ی راسهای لازم و هر زیر مجموعه ای از راسهای اشتاینر باشد.

راهنمایی: یک گراف سه لایه بسازید: لایه 1 شامل راسهای ضروری معادل هر عضو، لایه 2 شامل راسهای اشتاینر معادل هر مجموعه و لایه 3 شامل r.

همان طور که راهنمایی گفته است هر عضو مجموعه مرجع را یک راس ضروری در نظر می گیریم و هر مجموعه را یک راس اشتاینر در نظر می گیریم و با میانگین وزن اعضای آن به راسهای لازم متناظر آنها وصل می کنیم. چون این گراف همبند نیست یک راس r اضافه می کنیم و به همه ی راسهای اشتاینر آن را با هزینه 0 وصل می کنیم. (مثلا فرض کنید مجموعه تهی است). حالا با محاسبه ی درخت اشتاینر جهت دار، همه ی اعضای مجموعه مرجع انتخاب می شود و این کار با کمترین هزینه انجام می شود، پس جواب بهینه مساله پوشش مجموعه ای است. پس نمی تواند ضریب تقریب بهتری از این مساله که ضریب تقریب O(log n) دارد داشته باشد.

درخت اشتاینر و مساله فروشنده دوره گرد

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

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

قضیه: می توان مساله ی درخت اشتاینر را به درخت اشتاینر متریک تبدیل کرد بدون اینکه ضریب تقریب به هم بخورد.

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

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

برای هر یال گراف ثانویه هزینه ی آن از هزینه ی یال گراف اولیه کمتر مساوی است. پس هزینه ی جواب روی گراف ثانویه از هزینه ی جواب روی گراف اولیه کمتر مساوی است.

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

الگوریتم درخت اشتاینر متریک:

تا اینجا ثابت کردیم که حالت متریک را حل کنیم حالت معمولی هم حل می شود. حالا می خواهیم حالت متریک را حل کنیم.

MST راسهای لازم را حساب می کنیم و این یک جواب غیربهینه برای مساله است. (چون MST در P است و درخت اشتاینر در NP-hard). اما این جواب غیربهینه فاصله ی کمی تا جواب بهینه دارد (ضریب تقریب 2).

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

مثال tight: گراف با n راس لازم و یک راس اشتاینر را در نظر بگیرید. یال بین راس اشتاینر و راس لازم هزینه ی یک دارد و یال بین دو راس لازم هزینه ی 2 دارد. هر MST در این گراف 2(n-1) هزینه دارد، در حالی که جواب بهینه هزینه ی n دارد.

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

فروشنده دوره گرد: یک گراف کامل با یالهای وزندار نامنفی داده شده است، دور با کمترین هزینه را پیدا کنید که هر راس را دقیقا یک بار ببیند. (این مساله را نمی شود تقریب زد مگر اینکه P=NP باشد)

اثبات: برهان خلف: فرض کنید که یک الگوریتم تقریبی چند جمله ای باشد و ضریب آن را a(n) بگیرید. نشان می دهیم با این الگوریتم می توان تصمیم گیری مساله دور همیلتونی (فروشنده دوره گرد بدون وزن!) را حل کرد که در زمان چندجمله ای np-hard است. ایده ی اصلی کاهش از مساله ی دور همیلتونی به فروشنده دوره گرد است که یک گراف را به یک گراف کامل وزندار تبدیل می کند، به طوری که:

الف) اگر گراف اولیه دور همیلتونی داشته باشد، هزینه ی دور فروشنده دوره گرد بهینه در گراف ثانویه n است.

ب) اگر گراف اولیه دور همیلتونی نداشته باشد، هزینه ی دور فروشنده دوره گرد بهینه در گراف ثانویه بیشتر از a(n).n است.

در حالت الف، هزینه ی جواب بهینه از a(n).n کمتر/مساوی است و در حالت ب بیشتر است. پس می توان از آن برای تصمیم گیری وجود دور همیلتونی استفاده کرد. (پس اگر چنین کاری را بتوان انجام داد مساله ی np-hard را در زمان چند جمله ای حل کردیم.)

نحوه ی کاهش (reduction) هم ساده است. به هر یال گراف اولیه وزن 1 بدهید و برای ساخت گراف ثانویه به بقیه یالهایی که نبوده اند وزن a(n).n بدهید. حالا اگر گراف اولیه دور همیلتونی داشته باشد، هزینه ی جواب در گراف ثانویه n می شود، در غیر این صورت هر دور فروشنده دوره گرد در گراف ثانویه باید از یالی بگذرد که هزینه ی a(n).n دارد و در نتیجه هزینه ی آن از این مقدار بیشتر است.

الگوریتم ساده برای تقریب مساله فروشنده دوره گرد متریک با ضریب 2:

با حذف هر یال از فروشنده دوره گرد به یک MST برای گراف می رسیم، پس کران پایین را MST می گیریم.

الگوریتم:

1- یک MST روی گراف پیدا کن.

2- هر یال را دو برابر کن (بین دو راسی که قبلا یال بوده یک یال دیگر با همان وزن بگذار) و یک گراف اویلری به دست بیاور.

3- یک دور اویلری روی این گراف پیدا کن.

4- دوری را که راسهای گراف را به ترتیب آمدن آنها در دور (با راس تکراری!) اویلری می بیند برگردان.

(فکر کنم بهش میگن گذر، توی متن اصلی tour نوشته بود.)

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

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

اثبات: (دقیقا همان اثبات مساله ی قبل!)

مثال حالت بد: گراف کامل n راسی که یالهای آن وزنهای 1 و 2 دارند. یالهای بین یک راس v و بقیه راسها را وزن یک می دهیم و بقیه راسها هر کدام به دقیقا یک راس دیگر (به جز راس v) یال با وزن یک دارند و بقیه یالها وزن 2 دارند. پس تعداد یالهای با وزن 1 می شود 2(n-1) که یک ستاره و دور n-1 راسی می سازند. جواب بهینه روی دور حرکت می کند و قبل از اینکه به راس شروع برگردد از راس وسطی عبور می کند. این جواب هزینه ی n دارد. جواب الگوریتم ما MST است که مثلا می تواند گراف ستاره باشد، در این حالت گراف اویلری که از روی آن می سازیم دو یال با وزن 1 دارد و بقیه وزن 2 دارند، که در مجموع هزینه ی 2(n-1) دارد که دو برابر  جواب بهینه است.

بهبود الگوریتم به ضریب 3/2:

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

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

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

قضیه: این الگوریتم ضریب تقریب 3/2 برای فروشنده دوره گرد متریک دارد.

هزینه ی دور اویلری کمتر از هزینه ی MST + هزینه ی تطابق کامل راسهای فرد است؛ که این خودش کمتر مساوی جواب بهینه فروشنده دوره گرد + 1/2 جواب بهینه ی فروشنده دوره گرد است که می شود جمعا 3/2 جواب بهینه.

مثال tight: برای تعداد راس فرد، یک مسیر بسازید بعد هر راس را به راس بعدی نه راس بعدیش (دو تا راس جلوتر) وصل کنید همین کار را از راس آخر به اول هم انجام بدهید. همه ی این یالها را وزن 1 بدهید بعد از راس آخر به راس اول یک یال با وزن ceil(n/2) وصل کنید. MST که الگوریتم پیدا می کند همان مسیر است که هزینه ی n-1 دارد. تنها راسهای فردش هم راس اول و آخر هستند که با یال به وزن ceil(n/2) وصل می شوند. پس جواب الگوریتم می شود (n-1)+ceil(n/2). جواب بهینه هزینه ی n دارد: یال اول را برویم بعد یالهای پرشی را برویم. هزینه جواب الگوریتم 3/2 برابر جواب بهینه است.

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

کوتاهترین ابر رشته (فصل 2)

مجموعه متناهی از الفبا و n رشته s_i از این الفبا داده شده، کوتاهترین رشته s را بیابید که همه ی رشته های s_i زیر رشته آن باشند. بدون از دست رفتن عمومیت مساله فرض کنید هیچ رشته ای زیر رشته ی دیگری نباشد.

راه حل حریصانه: دو رشته با بیشترین اشتراک را اول قرار بدهیم، بقیه رشته ها را چک کنیم و رشته ای که پیشوند آن با پسوند رشته ی فعلی اشتراک بیشتری دارد انتخاب کنیم و همین کار را ادامه بدهیم.

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

از اینجا نتیجه می شود الگوریتم حریصانه ی قبلی ضریب 2 دارد و خوب نیست. حالا سعی می کنیم آن را بهبود بدهیم.

راه حل حریصانه 2: با حذف ترتیب انتخاب مجموعه ها می توانیم انتخاب حریصانه ی بهتری انجام بدهیم. همه ی ابررشته های ممکن را برای هر دو رشته ورودی حساب می کنیم (نه فقط دو تا ابر رشته ی بهینه ی آنها را، نمی دانم چرا؟؟).

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

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

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

(توی کتاب نگفته که چرا ابر رشته ها رشته مشترک ندارند یا اگر دارند چطور رشته های مشترک را حذف می کند و کاری می کند که یک رشته بیش از دو بار نیامده باشد.)

جواب نهایی شده ضرب ضریب تقریب این دو مساله: 2 * H(n)

تغییر یکی از موضوعات وبلاگ

احتمالا بخوام تقریبی رو حذف کنم. هم بخوام خودم بخونم هم تهش به همه بیشتر از من نمره بده اصلا ارزش نداره.

پوشش مجموعه ای - مرجع: motwani

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

الگوریتم: هر بار راس با بیشترین درجه را بردارید و همه ی یالهای متصل به آن را حذف کنید.

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

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

الف) حریصانه و با delta+1 رنگ (delta ماکسیمم درجه)

از یک راس شروع می کنیم و آنرا رنگ می کنیم و همه ی همسایه های آن را با رنگ دیگری رنگ می کنیم. این کار را برای همسایه های آن راس هم انجام می دهیم. اگر دو سر یک یال همرنگ بود، رنگ یک سر آن را عوض می کنیم: چون هر راس حداکثر delta همسایه دارد و ما delta+1 رنگ داریم این کار همیشه امکان پذیر است.

ب) یک الگوریتم برای رنگ آمیزی گراف 3-رنگ پذیر با O(sqrt(n)) رنگ بدهید.

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

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

7- ثابت کنید پوشش راسی حالت خاص پوشش مجموعه ای است.

پوشش مجموعه ای می گوید مجموعه ها اجتماعشان مجموعه مرجع شود و تعداد مجموعه های انتخاب شده کمینه باشد.

پوشش راسی می گوید راسهای انتخاب شده شامل حداقل یک سر هر یال باشند.

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

8- ثابت کنید پوشش مجموعه ای حریصانه ضریب تقریب H(k) دارد. (k=تعداد اعضای بزرگترین زیرمجموعه ی U)

(انتخاب حریصانه: cost(S)/(|S-C|) ماکسیمم شود.)

توی پستهای قبلی هست.

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

ادامه ی تمرینهای فصل 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 هستند) را زیاد کنیم که قبل از راس اول (مرکز ستاره) انتخاب شوند. 

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

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

?) 1/2 OPT <= ALG <= OPT

deg(Vi) >= deg_A(Vi)+deg_B(Vi)

ALG(Vi) = max( deg_A(Vi), deg_B(Vi) )

max(x,y) >= 1/2(x+y)

ALG(Vi) >= 1/2 ( deg_A(Vi)+deg_B(Vi) ) >= 1/2 deg(Vi)

OPT(Vi) = deg_A*(Vi) <= deg(Vi)

ALG = sum(ALG(Vi)) >= 1/2 sum(deg(Vi)) >= 1/2 OPT

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

(ایده: اجرای الگوریتم و انتخاب بدترین حالت ممکن در هر مرحله)

کران بالا:

مثال کرانها:

2- سوال قبل را با الگوریتم جستجوی محلی (local search) حل کنید: از دو مجموعه ی دلخواه شروع کنید، اگر با عوض کردن جای یک راس جواب بهتر شد این کار را انجام دهید. تا وقتی که دیگر نشود این کار را ادامه داد. ثابت کنید در زمان چندجمله ای الگوریتم تمام می شود (تعداد مراحل چندجمله ای است) و ضریب تقریب 1/2 است.

برای اثبات ضریب تقریب که همان اثبات سوال قبل است فقط دیگر قسمت اینکه جواب فعلی و جواب بعدی را نمی خواهد. (به جای جدا کردن روی A و B مستقیما می نویسیم درجه بزرگتر از نصف می شود.)

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

3- در یک گراف وزن دار برش با وزن بیشینه که گراف را k قسمت کند پیدا کنید. الگوریتم حریصانه با ضریب (1-1/k) بدهید. آیا این جواب tight است؟

انتخاب حریصانه: سود برداشتن / هزینه ی برداشتن

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

الگوریتم: اضافه کردن یک راس به یک مجموعه: وزن یالهای بین آن راس و راسهای مجموعه های دیگر / وزن یالهای بین آن راس و اعضای مجموعه خودش

cost(Vi, Sj) = sum_u_in_Sj( cost(u,Vi) ) / sum_u_not_in_Sj( cost(u,Vi) )

ALG(Vi) = max_Sj ( cost(Vi, Sj) ) <= 1/k sum_j (cost(Vi,Sj) )

W(Vi) = sum of weights of incident edges of Vi

sum_j(cost(Vi,Sj)) <= k*W(Vi)-W(Vi) = (k-1)W(Vi)

OPT(Vi) < W(Vi)

==> ALG < (k-1)/k OPT

مثال:

4- برش با وزن بیشینه جهت دار. الگوریتم با ضریب تقریب 1/4 بدهید.

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

(راه حل 2: local search)

ALG(Vi) = max( sum_u_S' (cost(Vi,u) , sum_u_S (cost(Vi,u)) )

ALG(Vi) >= 1/2 sum_u (cost(Vi,u))

ALG >= 1/2 sum_Vi sum_u(cost(Vi,u))

OPT <= sum_Vi sum_u( cost(Vi,u) )

ALG >= 1/4 OPT

5- با کمک سوال 2 (local search) و این حقیقت که برای گرافهای دوبخشی مساله پوشش راسی در زمان چندجمله ای حل می شود، یک الگوریتم تقریبی با ضریب lg delta بدهید که delta بیشترین درجه ی راسهای گراف است.

راهنمایی: زیرگراف به دست آمده برای سوال برش بیشینه را در نظر بگیرید (H). می دانیم H دوبخشی است و درجه ی هر راس آن از نصف درجه ی آن راس در G (گراف اصلی) بیشتر مساوی است.

می توانیم از تکنیک لایه ای استفاده کنیم و گراف H را هر بار بسازیم و یالهایی که تصمیم گرفتیم براشون رو حذف کنیم. هر بار نصف درجه ی راسها را بر می داریم حداقل، پس تقریب حداکثر log delta می شود.

6- رنگ آمیزی رئوس: گراف بدون جهت G داده شده، راسهای آن را طوری رنگ کنید که حداقل تعداد رنگ به کار برود و دو سر هر یال رنگ متمایز داشته باشند.

الف) یک الگوریتم حریصانه بدهید که G را با delta+1 رنگ، رنگ کند. (delta ماکسیمم درجه)

ب) یک الگوریتم برای گرافهای سه رنگ پذیر بدهید که O(sqrt(n)) رنگ بخواهد.

راهنمایی: برای هر راس، گراف القایی روی همسایه های آن، N(v)، دوبخشی است پس به صورت بهینه قابل رنگ کردن است. اگر v درجه ی بیشتر از sqrt(n) داشته باشد، v و همسایه هایش را با سه رنگ متمایز رنگ کنید. این کار را ادامه دهید تا هر راس درجه ی کمتر از sqrt(n) داشته باشد. بعد از الگوریتم بخش اول استفاده کنید.

تمرینهای فصل 1 کتاب

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

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

راهنمایی: راسها را دلخواه شماره گذاری کنید و مجموعه ی بزرگتر از بین یالهای از شماره کمتر به بیشتر و یالهای از شماره بیشتر به کمتر را بردارید. از چه شمایی برای کران بالای جواب بهینه استفاده می کنید؟

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

چیزی که باید ثابت کنیم:

1/2OPT<=ALG

1/2*OPT <= max(deg_>, deg_<)

OPT <= 2*max(deg_>,deg_<)

OPT <= |E|=deg_>+deg_< <= 2*max(deg_>,deg_<)

2- یک الگوریتم با ضریب تقریب 2 بدهید که این مساله را حل کند: یک تطابق ماکسیمال با کمترین تعداد اعضا روی یک گراف بدون جهت به دست بیاورد.

راهنمایی: از این حقیقت استفاده کنید که هر تطابق ماکسیمالی حداقل به اندازه ی نصف تطابق بیشینه یال دارد.

حل:

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

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

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

این دو نامساوی را بنویسیم خود به خود به جواب می رسیم:

1/2*|MM| <= OPT ==> |MM| <= 2*opt

ALG = |M| <= |MM|

==> ALG=|M| <= 2*OPT

3- الگوریتم تقریبی با ضریب 2 زیر را در نظر بگیرید که تعداد اعضای پوشش راسی را حساب می کند. یک درخت پیمایش عمقی (dfs) روی گراف G پیدا کنید و مجموعه ی S از همه ی راسهای غیر برگ این درخت را برگردانید. نشان دهید S یک پوشش راسی از G است و 

|S| <= 2.OPT

راهنمایی: نشان دهید که G یک تطابق با اندازه ی |S| دارد.

حل:

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

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