مساله های شبه LP

مساله های شبیه LP یا LP-type problem ها مساله هایی هستند که با همان ایده ی LP حل می شوند اما LP نیستند.

یکی از ایده هایی که به کار می رود ایده ی seidel است (تصادفی افزایشی).

مثال:

برای مجموعه ای از نقاط در صفحه کوچکترین دایره شامل همه ی نقاط را پیدا کنید.

پیدا کردن دایره: سه نقطه روی محیط آن یا دو نقطه روی قطر آن

الگوریتم تصادفی welz و Seidel

ایده: یک نقطه روی محیط را داریم.

تابع بازگشتی: circle(S,B) را تعریف می کنیم. در آن S مجموعه نقاط است و B نقاط روی محیط کوچکترین دایره ی محیطی این نقاط است.

شروع الگوریتم: circle(all points, empty)

حالت پایه: اگر S تهی بود یا B سه عضو داشت جواب را برگردان.

یک نقطه ی تصادفی از S را بردار و circle(S-{p},B) را صدا کن.

اگر نقطه ی p درون دایره افتاد همین جواب را برگردان، در غیر این صورت p روی محیط دایره می افتد و circle(S-{p},B U {p}) را برگردان.

( مثل استقرای قهقرایی :) )

زمان الگوریتم:

احتمال اینکه نقطه روی دایره بیفتند : 3 تقسیم بر n (شبیه 2 تقسیم بر n برای LP)

T(n,b) = T(n-1,b)+O(1)+3/n*T(n-1,b+1)

T(n,3) = O(1)

==>

T(n,2) <= T(n-1,1)+O(1)+T(n-1,3)=T(n-1,1)+O(1) ==> T(n,2) = O(n)

T(n,1) <= T(n-1,1)+O(1+3/n*n) ==> T(n,1) = O(n)

T(n,0) = T(n-1,0)+O(1)+3/n*T(n-1,1) <= T(n-1,0)+O(1)+3/n*O(n) = T(n-1,0)+O(1) ==> T(n,0) = O(n) 

تعمیم:

برای حالت d بعدی، زمان (d+1)!n به دست می آید.

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