روش تکراری برای رند کردن LP

منبع: http://www.cs.umd.edu/~hajiagha/NetDsgn11/Iterative-Methods-UMD.pdf

برای رند کردن LP روش‌های مختلفی هست:

- وقتی مقدار متغیرهای اعداد اعشاری بزرگ باشد، مثل پوشش رأسی، به نزدیک‌ترین عدد صحیح رند می‌کنیم. (رند کردن قطعی)

- رند کردن تصادفی، مثل مسایل پوشش و بسته‌بندی، در این مسایل هر متغیری را با احتمال مقدار اعشاری آن رند می‌کنیم. (برای متغیرهای صفر و یک)

- رند کردن با جاسازی متریک؟

مثل برش بیشینه

- روش اولیه-ثانویه (primal-dual)

- رند کردن تکراری؟

- ریلکس کردن تکراری؟

من خودم هم نمی‌دانم خیلی از این رند کردن‌ها چطوری کار می‌کنند و آنهایی را هم که می‌دانم نمی‌دانم چرا درست کار می‌کنند. اما این ارائه در مورد رند کردن تکراری است.

رند کردن تکراری:

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

الگوریتم: برای این کار LP را به شکل یک covering LP بنویسید. بعد باید ثابت کنید که متغیر با مقدار بزرگ هست. متغیرهای با مقدار بزرگ را رند کنید. قیدها را طوری تغییر بدهید که باقیمانده‌ی مسأله را مدل کنند. (به نظرم منظورش جایگذاری است.) این کار را تکرار کنید تا همه‌ی متغیرها مقدار صحیح پیدا کنند.

.....

فشرده‌سازی بازگشتی و ماینورهای گراف

k شئ را حذف می‌کنیم تا به یک ویژگی دست پیدا کنیم.

مثال: k رأس را حذف کنید تا گراف دوبخشی شود.

زیرگراف القایی غیر مجاز: دور فرد.

ماینورهای گراف:

گرافی که با فشرده‌سازی یال، حذف یال یا حذف رأس به دست بیایند.

مثال: مثلث یک ماینور گراف G است اگر G جنگل نباشد (دور داشته باشد).

درخت جستجوی محدود شده

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

هر قانون شاخه شدن حداکثر b(k) شاخه می‌سازد و هر اعمال قانون شاخه شدن پارامتر را کاهش می‌دهد؛ مسأله را می‌توان در زمان O*(b(k)^k) حل کرد.

در بسیاری موارد می‌توان این کران بالا را با تحلیل بهتر بهبود داد.

(دقت کنید که b تابعی از k است.)

لم آفتابگردان

(من الآن به این نتیجه رسیدم که می‌توانم از کلمات کلیدی به جای نوشتن مبحث در عنوان استفاده کنم!)

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

لم (اردوش، رادو، 1960): اگر اندازه یک مجموعه از مجموعه‌ها بیشتر از 

(p-1)^d d!

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

کاهش تاج (crown reduction): الگوریتم‌های پارامتر ثابت

اگر رأسهای گراف را به مجموعه‌های C H B افراز کنیم به طوری که C یک مجموعه‌ی مستقل باشد و هیچ یالی بین C و B نباشد و بین C و H یک تطابق باشد که همه‌ی H را بپوشاند یک کاهش تاج داریم.

برای مسأله‌ی پوشش رأسی می‌توانیم C و H را از گراف حذف کنیم و k-|H| رأس دیگر پیدا کنیم چون همه‌ی C توسط H پوشش داده می‌شود. اینکه H جزو جواب بهینه است از اینجا مشخص می‌شود که رأسهای C فقط به H وصل هستند.

قضیه: اگر یک گراف بدون رأس تنها و عدد k داده شده باشد، در زمان چندجمله‌ای:

یا می‌توانیم یک تطابق با k+1 یال پیدا کنیم که نتیجه می‌دهد مسأله جواب ندارد.

یا می‌توانیم یک کاهش تاج پیدا کنیم که مسأله کوچکتر می‌شود.

یا می‌توانیم نتیجه بگیریم که گراف حداکثر 3k رأس دارد (یک کرنل 3k رأسی است). (در نتیجه می‌توانیم در نمایی بر حسب k حلش کنیم.)

نتیجه: یک کرنل 3k رأسی برای پوشش رأسی به دست می‌آید.

هسته سازی(kernelization): الگوریتم‌های پارامتر ثابت

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

هسته‌سازی یک تبدیل چندجمله‌ای است که یک نسخه از مسأله را به یک نسخه‌ی با پارامتر کوچکتر تبدیل می‌کند که اندازه‌ی این نمونه‌ی جدید از تابعی از پارامتر کمتر باشد و جواب آن تغییر نکند. (نسخه‌ی تصمیم گیری مسأله)

*اگر یک الگوریتم قابل کرنل‌سازی باشد، FPT است.

اثبات: نسخه‌ی کوچکتر بر حسب k نمایی است (چون در کرنل خود اندازه مسأله برحسب k نمایی است) پس آن را با brute force (امتحان کردن همه‌ی حالت‌ها) حل می‌کنیم.

*عکس قضیه: هر مسأله‌ی FPT دارای یک الگوریتم کرنل‌سازی است.

اثبات: حالت بندی می‌کنیم. اگر f(k)<n باشد، که مسأله چندجمله‌ای حل می‌شود و آن را حل می‌کنیم و یک نسخه‌ی بدیهی از مسأله با همان جواب را به عنوان کرنل برمی‌گردانیم.

اگر n<f(k) باشد هم خودش یک کرنل است و خودش را برمی‌گردانیم.

سوالهای پایان ترم داده‌های حجیم

۱- قطر یک درخت که یالهای آن داده شده است را حساب کنید. پیچیدگی I/O الگوریتم شما چقدر است؟
۲- همان سوال محاسبه‌ی عنصر اکثریت وقتی دو تا جویبار داده را به هم بچسبانیم.
۳-در پیمایش Van Emde Boas زمان جستجو را به صورت دقیق حساب کنید و ثابت کنید که 4 log_B N/B در بدترین حالت می‌شود و در حالت متوسط 2 log_B N/B می‌شود.
۴- همان سوال نمونه سوالها که گفته بود رنگ یک مولفه همبندی را تغییر بدهید.