فصل 9 تقریبی Bin Packing

مساله: n شی با اندازه های a1,..,an در بازه 0 تا 1 (بزرگتر از 0) داده شده اند. بسته بندی به سطل های با اندازه 1 پیدا کنید که تعداد سطلهای لازم را مینیمم کند.

الگوریتم تقریب 2:

First-Fit: ترتیب دلخواه از اشیا را در نظر می گیریم. در گام i-ام لیستی از سطلهای نیمه پر داریم: B1,..,Bk. سعی می کنیم شی بعدی (ai) را در یکی از این جعبه ها بگذاریم (به همین ترتیب). اگر در هیچ کدام از این سطلها جا نشد، یک سطل جدید B(k+1) باز می کنیم و ai را درون آن می گذاریم. اگر الگوریتم از m سطل استفاده کند، حداقل m-1 سطل بیش از نصفشان پر است. {چون اگر کمتر از نصف قبلی پر باشد و کمتر از نصف سطل جدید هم پر باشد این نصفه را می توانستیم در همان سطل قبلی بریزیم. پس سطل نیمه پر نداریم مگر سطل آخری.} یعنی:

sum_i_1_n(ai) > (m-1)/2

چون جمع وزن اشیا کران پایین روی جواب بهینه است، {همه ی سطلها کامل پر شده باشند} پس

(m-1)/2 < OPT ==> m-1 <2OPT ==> m <= 2OPT

اما اشکال این است:

قضیه 9.2: برای هر اپسیلون مثبت، هیچ الگوریتم تقریبی نیست که 3/2-epsilon تقریب برای مساله بسته بندی سطلی باشد. (مگر اینکه P=NP باشد.)

اثبات: اگر چنین الگوریتمی بود، مساله NP-سخت تصمیم گیری وجود افرازی که n عدد نامنفی a1,...,an را به دو مجموعه که جمع اعضای هر کدام 1/2sum(ai) باشد را حل می کند. بدیهی است که جواب این سوال "بله" است اگر و تنها n شی بتوانند به دو سطل با اندازه ی 1/2sum(ai) ها بسته بندی شوند. اگر جواب "بله" باشد الگوریتم تقریبی با ضریب 3/2-epsilon یک جواب بهینه برای بسته بندی می دهد و مساله افراز را حل می کند.

{حس می کنم باید جایی در این اثبات تقسیم بر مجموع می کرد که اندازه ی اشیا بین 0 و 1 شود!}

9.1. یک شمای تقریبی چندجمله ای مجانبی

لم 9.4: اگر K یک عدد صحیح نامنفی ثابت و اپسیلون ثابت داده شده باشد. اگر هر شی در بسته بندی سطلی اندازه اش حداکثر اپسیلون باشد و تعداد اندازه های مختلف K باشد، الگوریتم چندجمله ای هست که این مساله را به صورت بهینه حل می کند.

اثبات: تعداد اشیای سطل کمتر از یک بر اپسیلون است. (M). پس تعداد سطلهای با میزان پر بودن متمایز کمتر از انتخاب M از M+K است. (R). (تمرین 9.4). که یک ثابت بزرگ است. بدیهی است که تعداد سطلهای به کار رفته حداکثر n است. {هر شی در یک سطل!}. پس تعداد بسته بندی های ممکن کمتر از انتخاب R از R+n است که چندجمله ای برحسب n است. (تمرین 9.4). شمارش اینها و انتخاب بهترین بسته بندی جواب بهینه را می دهد.

لم 9.5: به ازای اپسیلون مثبت ثابت، نسخه ای از مساله بسته بندی سطلی را که در آن اشیا اندازه حداقل اپسیلون دارند در نظر بگیرید. یک الگوریتم تقریبی با زمان چندجمله ای هست که این مساله را با تقریب 1+epsilon حل می کند.

اثبات: فرض کنید I نمونه ای از مساله ورودی باشد. اشیا را به ترتیب اندازه شان مرتب کنید و آنها را به K=ceil(1/epsilon^2) دسته افراز کنید که هر دسته حداکثر Q=floor(n*epsilon^2) شی دارد. توجه کنید که دو دسته ممکن است اشیای هم اندازه داشته باشند.

نمونه ای از مساله (J) را با رند کردن اندازه ی هر شی به اندازه ی بزرگترین شی آن دسته بسازید. نمونه J حداکثر K اندازه شی متمایز دارد.

پس طبق لم 9.4 می توانیم جواب بهینه برای J پیدا کنیم. بدیهی است که این بسته بندی برای مساله اولیه هم جواب معتبر است. در ادامه نشان می دهیم که جواب بهینه J یک تقریب 1+اپسیلون برای جواب بهینه I است.

یک نمونه ی J' از مساله می سازیم که در آن وزن هر شی را به کمترین وزن آن دسته رند می کنیم. بدیهی است که جواب بهینه J' کمتر از جواب بهینه مساله است. مشاهده می کنیم که یک بسته بندی برای J' برای همه اشیا به جز Q تا بزرگترین شی J می دهد. (تمرین 9.6) پس:

OPT(J) <= OPT(J') + Q <= OPT(I)+Q

چون هر شی I اندازه اش حداقل اپسیلون است پس OPT(I) >= n*epsilon است پس Q = floor(n*epsilon^2) <= epsilon*OPT. پس حکم نتیجه می شود.

قضیه 9.3: برای هر اپسیلون مثبت کمتر مساوی 1/2 یک الگوریتم تقریبی A_epsilon هست که زمان اجرای چندجمله ای بر حسب n دارد و مساله بسته بندی سطلی را با حداکثر (1+2epsilon) * بهینه+1 سطل حل می کند.

دنباله ی الگوریتم های A_epsilon یک PTAS مجانبی برای بسته بندی سطلی است؛ چون برای هر اپسیلون مثبت یک N مثبت وجود دارد و یک الگوریتم چندجمله ای در این دنباله هست (B) که تقریب 1+اپسیلون برای همه ی ورودی هایی که هزینه جواب بهینه بیشتر مساوی N دارند می دهد. 

اثبات: فرض کنید I نمونه ی داده شده باشد و I' را با حذف اشیای با وزن کمتر از اپسیلون از روی آن بسازید. طبق لم 9.5 برای I' بسته بندی با تقریب 1+اپسیلون برابر جواب بهینه برای I' هست. بعد اشیای با وزن کمتر از اپسیلون را با روش First-Fit در سطلهای I' می گذاریم. سطلهای جدید به شرطی ساخته می شوند که در سطلهای قبلی جا نباشد.

اگر هیچ سطل جدیدی لازم نشد که خود به خود تقریب 1+اپسیلون هست. در حالت دوم، M را جمع سطلهای به کار رفته بگیرید. بدیهی است که همه ی سطلها به جز آخری به اندازه ی 1-اپسیلون پر خواهند بود. پس جمع اشیای I حداقل (M-1)(1-epsilon) است. چون این یک کران پایین برای جواب بهینه است به دست می آوریم:

M <= OPT/(1-epsilon)+1 <= (1+2*epsilon)OPT+1

که از فرض اپسیلون کمتر مساوی 1/2 برای نامساوی سمت راست استفاده کردیم. پس برای هر مقدار اپسیلون بین 0 تا 1/2 یک الگوریتم چندجمله ای داریم که تقریب بالا را دارد.

الگوریتم 9.6: الگوریتم A_epsilon

1) همه ی اشیای با وزن کمتر از اپسیلون را حذف کن.

2) اندازه ها را رند کن تا تعداد وزن های متمایز اشیا ثابت باشد (لم 9.5).

3) بسته بندی بهینه را به دست بیاور. (لم 9.4).

4) از این بسته بندی برای اندازه های اصلی استفاده کن.

5) اشیای با وزن کمتر از اپسیلون را با First-Fit بسته بندی کن.