sub-linear time algorithm

http://people.csail.mit.edu/ronitt/sublinear.html

فصل 12 وزیرانی: دوگان LP

این قبلا قسمت اولش را توضیح داده ام!

قضیه 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)

فصل 11 وزیرانی: فروشنده دوره گرد تقریبی

در این فصل یک PTAS برای حالت خاصی از فروشنده دوره گرد می دهیم که در آن نقاط در فضای d بعدی اقلیدسی داده شده اند. مثل قبل ایده ی اصلی PTAS تعریف یک جواب دانه درشت {منظور جوابی است که جزئیات آن حذف شده باشد} بر حسب پارامتر خطای اپسیلون و پیدا کردن جواب آن با برنامه ریزی پویا (dp) است. ویژگی این مساله این است که این بار به طور قطعی نمی توانیم جواب دانه درشت را مشخص کنیم و به صورت احتمالی این کار را انجام می دهیم.

مساله 11.1. فروشنده دوره گرد افلیدسی: برای d ثابت، n نقطه در R^d داده شده است، مساله پیدا کردن دور با کمترین طول گذرنده از n نقطه است. فاصله ی بین دو نقطه x و y فاصله ی اقلیدسی بین آنهاست. (جذر مجموع توان 2 تفاضل ابعاد متناظرشان!)

11.1. الگوریتم

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

جعبه محیطی (bounding box) یک نمونه از مساله کوچکترین مربع با اضلاع موازی محورهاست که همه ی نقاط درون آن باشد. با کمی تقسیم بندی در ورودی می توانیم فرض کنیم طول ضلع این مربع L، برابر 4n^2 است و یک توری به ضلع یک روی آن طوری تعریف شده که هر نقطه روی یک راس توری می افتد. (تمرین 11.1). به علاوه بدون از دست رفتن عمومیت مساله فرض کنید n توان 2 باشد و قرار بدهید: L=2^k که k=2+lg n

"برش اولیه" جعبه محیطی یک افراز بازگشتی به مربع های کوچکتر است. پس مربع L * L به چهار مربع L/2 * L/2 تقسیم می شود و ... . این تقسیم را به صورت یک درخت چهارتایی (درجه هر راس 4) می بینیم T که ریشه آن جعبه محیطی است. فرزندان آن 4 مربع L/2*L/2 اند. گره های درخت T دارای level هستند. ریشه 0 و فرزندانش 1 و ... . پس مربع سطح iام ابعادش L/2^i * L/2^i است. تا رسیدن به مربع 1*1 ادامه می دهیم. T عمق k=O(log n) دارد. منظور از یک "مربع مفید" مربعی است که نمایانگر یک راس درخت باشد. {خلاصه همان quad-tree است!}

اپسیلون را هم روی ارتفاع درخت تعریف کرده است. (درشت دانه بودن). می خواهیم ثابت کنیم که مسیری که ساخته می شود 1+اپسیلون تقریب است. قبل از آن نشان می دهیم که چرا این موضوع PTAS بودن را نتیجه می دهد.

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

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

لم 11.3: گشت توصیف شده در بالا را به طور بهینه می توان در زمان n^O(1/epsilon) به دست آورد. (2 به توان عمق درشت شده!)

اثبات: حالت بندی، dp، پرانتزگذاری صحیح

11.2. اثبات درستی

همیشه طول دور تقریب 1+اپسیلون جواب بهینه نیست. به جای این خانواده ی بزرگتری از انحرافها را می سازیم و نشان می دهیم که برای هر چیدمان نقاط حداقل نصف حالتها شرایط مورد نظر را دارند. یکی را تصادفی بر می داریم. ...

لم 11.4: تعداد تقاطع های گشت جواب کمتر مساوی 2 برابر جواب بهینه است.

در ادامه حقیقتی که باعث به دست آمدن PTAS برای مساله می شود آمده است.

قضیه 11.5: برداشتن a و b (شروع خطوط تقسیم) به صورت تصادفی یکنواخت از بازه ی 0-L باعث افزایش میانگین هزینه ساخت جواب بهینه به میزان کمتر از 2 اپسیلون برابر جواب بهینه می شود.

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

نکته 11.6: ایده های منجر به قضیه 11.5 به صورت زیر خلاصه می شوند. چون خطوط سطح پایینتر مربع های بزرگتری مجاورشان است، ما مجبور بودیم وسط ضلع های آنها را دورتر بگذاریم تا هر کدام حداکثر 4 برابر عمق دانه درشت وسط ضلع داشته باشند (که باعث می شود dp در زمان چندجمله ای امکان پذیر باشد). اما این باعث شد که ما نمونه های بیشتری بسازیم که هیچ جواب کوچکی نداشتند. (تمرین 11.3). به علاوه تعداد خطوط کمتری سطح های پایین دارند. (قضیه 11.5).

نتیجه 11.7: احتمال اینکه تصادفی یکنواخت شروع توری را انتخاب کنیم و طول گشت حداکثر 4 اپسیلون برابر جواب بهینه شود بیشتر مساوی 1/2 است.

PTAS: یک تقسیم بندی تصادفی می سازیم و جواب بهینه را برای آن پیدا می کنیم (با dp). (طبق لم 11.3). الگوریتم را می تواینم با امتحان کردن همه ی حالتهای شیفت و چاپ کمترین در بین آنها غیرتصادفی کنیم.

قضیه 11.8: برای فروشنده دوره گرد اقلیدسی در صفحه یک PTAS هست.

فصل 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 بسته بندی کن.

اسلایدهای Agarwal

http://www.cs.duke.edu/~pankaj/slides/

پوشاننده ها (هندسه محاسباتی)

http://bayanbox.ir/id/2678559934970633426

(اسلاید انگلیسی- دانشگاه یزد)

برنامه ریزی حرکت روبات و فاصله مینکوفسکی

file:///C:/Users/Sepideh/Desktop/Chapter13.pdf

(فارسی: همان فصل کتاب هندسه محاسباتی است)

تحلیل مرتب سازی موازی با رابطه بازگشتی

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-895-theory-of-parallel-systems-sma-5509-fall-2003/lecture-notes/lecture2.pdf

خود درس هم اسلایدها و توضیحات جالبی داشت.

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

8.1- الگوریتم حریصانه برای کوله پشتی را در نظر بگیرید. اشیا را بر حسب نسبت سود به اندازه ی آنها نزولی مرتب کنید و حریصانه اشیا را به این ترتیب بردارید. نشان دهید حالتی هست که این الگوریتم به میزان دلخواه بد عمل کند.

من هر مثالی به ذهنم رسید دو برابر بیشتر نشد. :)

MEB در ابعاد بالا و مدل جویبار داده

https://cs.uwaterloo.ca/~tmchan/blur_wads.pdf