منبع: صفحه ۱۸۵ کتاب Approximation Algorithms and Semidefinite Programming نوشته‌ی Bernd Gärtner, Jiří Matoušek
(کلاً کتاب خوبی نبود ولی اتفاقی این سوال رو توش دیدم که سوال اول تمرینهاست! البته من حل خودم رو تحویل میدم.)
این سوال دوم را به خاطر اینکه در مورد خوشه‌بندی است می‌آورم:
http://www.lamsade.dauphine.fr/~bazgan/Papers/icalp98.pdf
می‌خواهیم دو زیرمجموعه مجزا از اشیا انتخاب کنیم که نسبت مجموع آنها مینیمم شود.
قسمتی از این مسأله که تکراری است و نیاز به حساب کردن همه‌ی حالت‌ها ندارد، این است که همه‌ی زیرمجموعه‌های مجموعه اصلی را که حساب کنیم شامل هر دو مجموعه هست. پس کافی است حالتی را پیدا کنیم که اختلاف آنها مینیمم شود. سپس به ازای هر سود چک می‌کنیم که دو زیرمجموعه مجزا هستند که آن سود را بدهند یا نه. چک کردن این کار با توجه به اینکه زیرمجموعه‌ها را با آرایه‌های دودویی نشان داده‌ایم ساده است.
به جای دور فروشنده دوره‌گرد مسیر فروشنده دوره‌گرد را به دست بیاورید.
من مقاله‌ای که جواب این سوال در آن هست را آپلود کردم اما اثباتش هم طولانی بود هم عجیب.
دریافت
حجم: 383 کیلوبایت
(Bin packing)
*تعدادی شئ با اندازه‌های بین ۰ و ۱ داریم می‌خواهیم آنها را در کمترین تعداد سطل با اندازه یک جا بدهیم.
این مسأله را نمی‌توان در زمان چندجمله‌ای بهینه حل کرد، اما می‌خواهیم نسخه‌ی دیگری از آن را بسازیم که در زمان چندجمله‌ای قابل حل است و از آن برای تقریب زدن مسأله اصلی استفاده کنیم.
*تعدادی شئ با اندازه‌های بین e(اپسیلون) و ۱ داریم که حداکثر K اندازه مختلف دارند و می‌خواهیم آنها را در کمترین تعداد سطل با اندازه یک جا بدهیم.
این مسأله را می‌توان در زمان چندجمله‌ای به صورت بهینه حل کرد. راه حل بهینه برای حل کردن آن امتحان کردن همه‌ی حالت‌های ممکن است.
شرطی که روی حداقل اندازه‌ی اشیا گذاشتیم باعث محدود شدن حداکثر تعداد اشیای هر سطل می‌شود:
تعداد حالت‌های مختلف هر سطل را به صورت زیر حساب می‌کنیم:
تعداد حالت‌های R سطل متفاوت را هم به صورت زیر حساب می‌کنیم:
پس تعداد کل حالت‌های مسأله چندجمله‌ای شد. دقت کنید که توان (R) به اپسیلون وابسته است و n اندازه مسأله ورودی است.
*حالا می‌خواهیم مسأله‌ی اصلی را تنها با شرط اضافه وزن اشیا بیشتر مساوی اپسیلون را با کمک این مسأله حل کنیم. برای این کار باید تعداد وزن‌های متمایز اشیا حداکثر K شود.
راه حل ۱ که خوب نیست: وزن اشیا را بر p/K تقسیم می‌کنیم که p ماکسیمم وزن اشیا است. با این کار وزن اشیا از بازه‌ی ۰ تا p به بازه‌ی ۰ تا K می‌رود. حداکثر تقریبی که این کار در وزن اشیا ایجاد می‌کند p/K است. (چون جزء اعشاری بین ۰ و ۱ است.) این مقدار تقریب مورد نظر ما در مسأله نیست و متاسفانه به p هم بستگی پیدا می‌کند.
راه حل ۲: در روش قبل ما تعداد وزن‌هایی که داریم احتمالا خیلی از K کمتر خواهد بود (چون در صورتی که همه‌ی وزن‌ها اعداد متوالی باشند K می‌شود). به همین دلیل مسأله را به چند زیرمسأله از مسأله‌ی حالت خاص که می‌توانیم آن را حل کنیم تبدیل می‌کنیم. این کار را طوری انجام می‌دهیم که شرط قبلی حفظ شود یعنی در هر دسته حداکثر K اندازه متمایز داشته باشیم.
حداکثر تعداد زیرمسأله‌های ساخته شده Q است (که در زیر مقدار آن آمده است). حالا K را طوری تعیین می‌کنیم ضریب تقریب مجموع وزن اشیا در جواب بهینه و این جواب حداکثر به اندازه اپسیلون فرق داشته باشد.
* حل مسأله اصلی
ما هنوز از یکی از اطلاعاتی که از مسأله داریم استفاده نکرده‌ایم. اگر اشیا وزن بیشتر مساوی ۰.۵ داشته باشند، می‌توانیم جواب بهینه آن را در زمان خطی به دست بیاوریم. چون در هر سطل حداکثر یک شئ قرار می‌گیرد. اگر اشیا وزن کمتر از ۰.۵ داشته باشند، آنها را حریصانه در جعبه‌ها می‌چینیم و به الگوریتم با ضریب تقریب ۱+۲*اپسیلون می‌رسیم.
مسأله را به دو قسمت تقسیم می‌کنیم: اشیای با وزن بیشتر از اپسیلون و اشیای با وزن کمتر مساوی اپسیلون
ثابت می‌کنیم اضافه کردن اشیای با وزن کمتر مساوی اپسیلون ضریب تقریب الگوریتم قبل را به هم نمی‌زند.
وزیرانی:
۱- مقدمه: پوشش رأسی، کران پایین برای جواب بهینه، تطابق بیشینه، دوگان LP و قضیه مینیمم-ماکسیمم، تبدیل مسأله‌های دیگر به پوشش رأسی
۲- الگوریتم‌های ترکیبیاتی-پوشش مجموعه‌ای: الگوریتم حریصانه، کران تطبیق‌پذیر و ضریب تقریب H(n)، مثال tight برای ضریب تقریب، تکنیک لایه‌ای: حل مسأله‌های دیگر با پوشش مجموعه‌ای، بهبود ضریب تقریب با پیدا کردن کران بهتر (تطبیق پذیر)، هرس فضای نمونه و پیشامد برای بهبود ضریب تقریب (تطبیق پذیر)
۳- الگوریتم‌های ترکیبیاتی-فروشنده دوره‌گرد و درخت اشتاینر: تبدیل یک مساله به مساله دیگر با حفظ ضریب تقریب، متریک کوتاهترین مسیر و بستار متریک، تقریب ناپذیری، جایگزین کردن دو یال با یک یال در گراف کامل متریک، ترکیب دو راه حل مسأله برای رسیدن به ضریب تقریب بهتر
۴- الگوریتم‌های ترکیبیاتی- چندبرش و k-برش، تبدیل مسأله خواستار هزینه مینیمم و مسأله خواستار اعضای بهینه، تغییر هزینه با حذف و اضافه کردن عضو (تطبیق پذیر)، مثال tight دارای اپسیلون، درخت گومری-هو، خلاصه کردن مسأله با حفظ هزینه
۵- الگوریتم‌های ترکیبیاتی-k-مرکز: هرس پارامتری، توانی از گراف (ماتریس مجاورت)
*۶- پوشش رأسی با فیدبک: جمعی بودن هزینه، مدل کردن با رشته دودویی، تکنیک لایه‌ای برای هزینه جمعی، حالت‌بندی و انتخاب بهینه برای قسمتی از مسأله
*۷- کوتاهترین ابررشته: پیدا کردن کران برای مجموع خطا در محاسبه ضریب تقریب، تبدیل به مسأله‌ی با ضریب تقریب بهتر با تغییر هزینه، تقریب قسمت‌های مختلف مسأله
۸- کوله‌پشتی: شمای تقریبی، الگوریتم شبه چندجمله‌ای، رندکردن بیتی، برنامه نویسی پویا برای به دست آوردن جواب بهینه مسأله رند شده، وجود شمای تقریبی چندجمله‌ای کامل و np-سخت بودن قوی، رند کردن برای رسیدن به مقدار لازم برای رسیدن به تقریب داده شده
۹- سطل‌بندی: شمای تقریبی مجانبی، حل مسأله برای جوابهای بهینه کوچک و رند کردن مسأله‌های بزرگ به کوچک، استفاده از الگوریتم‌های تقریبی برای حالت‌های کوچک
*۱۰- کوتاهترین برنامه: کران پائین دوتایی (ترکیبی)، هزینه پارامتری و جستجوی دودویی برای به دست آوردن پارامتر بهینه، ثابت فرض کردن یک پارامتر، شمای تقریبی چندجمله‌ای
*۱۱- فروشنده دوره‌گرد اقلیدسی: به دست آوردن جواب دانه درشت به صورت تصادفی، جعبه محیطی، تقسیم صفحه با شیفت دادن تصادفی مجموعه خطوط، درخت چهارتایی، توری سلسله مراتبی
۱۲- الگوریتم‌های بر مبنای LP-دوگان LP، قضیه دوگان ضعیف، شرایط بهینه بودن جواب، روابط مینیمم و ماکسیمم، integer programming، رند کردن LP، شمای اولیه-ثانویه، روش dual fitting، فاصله صحیح بودن یک تبدیل LP (نسبت صحیح بودن)، پیشگوی جداکننده
اگر Y یک الگوریتم (a,b)-تقریبی برای X باشد یعنی
X <= Y <= a.X+b
http://ce.sharif.edu/courses/92-93/2/ce726-1/assignments/files/assignDir3/exercises1.pdf
http://courses.csail.mit.edu/6.854/current
سوالها جواب دارند! :)
http://sarielhp.org/teach/notes/rand_alg/notes.pdf
این قبلا قسمت اولش را توضیح داده ام!
قضیه 12.2: قضیه ضعیف دوگان
اگر x=(x1,...,xn) و y=(y1,...,ym) به ترتیب دو جواب مجاز برای مساله های اصلی و دوگان باشند، داریم:
sum_j_1_n(cj*xj) >= sum_i_1_m(bi*yi)
اثبات: چون y دوگان پذیر است و xjها نامنفی هستند، داریم:
sum_j_1_n(cj*xj) >= sum_j_1_n( sum_i_1_m(aij*yi) * xj )
مشابه همین را برای x می نویسیم و حکم نتیجه می شود.
قضیه 12.3: (شرایط سستی مکمل): اگر x و y به ترتیب جوابهای مجاز مساله و دوگان آن باشند. آنگاه x و y هر دو بهینه اند اگر و تنها اگر شرایط زیر صادق باشند:
اولیه: به ازای هر j بین 1 تا n یا xj=0 باشد یا sum(aij yi) = cj
و
دوگان: به ازای هر i بین 1 تا m یا yi = 0 باشد یا sum(aij xj) = bi باشد.
(تا سر 12.2)
