Algorithmic Techniques for Massive Data

http://sublinear.wikischolars.columbia.edu/Lectures+and+Scribes

Extensive-form game

https://www.cs.umd.edu/users/nau/game-theory/3b%20Extensive-form%20games.pdf

نکته در استفاده از LP برای به دست آوردن الگوریتم تقریبی بهتر

من در یک مقاله دیده بودم که مثلاً برای به دست آوردن p-نرم، به جای اینکه برای خودش بنویسد، برای توان p-ام اش نوشته بود. البته آنجا احتمالاً دلیل این بود که می‌خواست محدب باشد که بتواند با convex programming حلش کند، اما دلیل نمی‌شود که نشود ازش استفاده کرد.

امروز سعی می‌کردم که به جای تابع هدف مسئله، از جمع تابع هدف با یک مقدار مثبت و مستقل از آن تابع هدف استفاده کنم. در نتیجه‌ی این کار جمع آنها وقتی مینیمم می‌شد که هر کدام مینیمم بشوند. در مسئله‌ای که من رویش کار می‌کردم تقریب از رند کردن متغیرها می‌آمد و من فکر می‌کردم که با اضافه کردن یک پارامتر دیگر می‌توانم کاری کنم که متغیرها به مقدارهای صحیح نزدیک‌تر بشوند.

خلاصه اینکه خیلی دارم سعی می‌کنم دلیل اینکه LP بدتر از حریصانه جواب می‌دهد را پیدا کنم چون الآن برای اثبات ضریب تقریب و حالت‌های دیگر مسئله به مشکلات جدی برخوردم. هنوز هم نمی‌دانم این iterative rounding باعث بهتر شدن کران تقریب در LP می‌شود یا نه. بهترین ایده‌ام تا الآن همینی بود که گفتم.

Convex Optimization Theory

مرجع: Convex Optimization Algorithms

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

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

Nested Satisfiability

مرجع: Selected Papers on Design of Algorithms

این مسئله در زمان چندجمله‌ای قابل حل است و حالتی از SAT است که در آن عبارت‌ها ساختار سلسله مراتبی دارند.

اگر m عبارت با این خاصیت و n متغیر داشته باشیم، حداکثر 2m+n جمله داریم.

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

روش تکراری برای رند کردن 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 رأسی برای پوشش رأسی به دست می‌آید.