Approximating the Expansion Profile and Almost Optimal Local Graph Clustering

http://arxiv.org/abs/1204.2021

http://msrvideo.vo.msecnd.net/rmcvideos/170891/dl/170891.pdf

http://arxiv.org/pdf/1204.2021v3.pdf

نظریه طیفی گرافها

Spectral graph theory

http://www.cs.ucsb.edu/~veronika/MAE/lecturesspectralgraphtheory_chung.pdf

تمبر خوارزمی

http://talg.acm.org

"Muhammad al-Khowarizmi, from a 1983 USSR commemorative stamp scanned by Donald Knuth"

الگوریتم تصادفی هارپلد

http://sarielhp.org/teach/notes/rand_alg/notes.pdf

معضل جدی

من تنهایی حوصله ام سر میره وبلاگ بنویسم. باید یکی دیگه باشه که وبلاگش را چک کنم ببینم اون هم داره یه کاری می کنه.

دارم سعی می کنم وبلاگهای دیگه و آدمهای دیگه رو پیدا کنم..

فصل 3 vladlen

کاربردهای اپسیلون-نت

*arrangement & point location

-مکان یابی نقطه در arrangement

مکان یابی را به صورت شمارش تعداد ابرصفحه هایی که نقطه کوئری زیر آنهاست، تعریف می کنیم.

ساختمان داده ای که به کار می بریم یک درخت است که در هر راس آن یک زیرمجموعه از ابرصفحه ها است. ریشه کل صفحه هاست. به ازای هر گره از درخت، به صورت بازگشتی زیردرخت آن را می سازیم. فرض کنید کلا n ابرصفحه داشته باشیم. اگر به ازای یک ثابت سراسری n0 بدانیم n<= n0 است این گره یک برگ است و بازگشت تمام می شود. در غیر این صورت ست سیستم (کل صفحات، صفحاتی که اشتراک یک d-simplex در صفحه اقلیدسی d بعدی دلتا با آنها تهی نباشد) می سازیم. این یک زیرسیستم از ست سیستم است که بعد VC آن حداکثر O(d^3 log d) است. پس بعد VC ست سیستم ما حداکثر O(d^3 log d) است که O(1) است چون d را ثابت فرض کردیم. پس قضیه اپسیلون-نت نتیجه می دهد که با نمونه گیری تصادفی در زمان O(n) می توانیم یک 1/r-نت بسازیم برای ست سیستم مان که اندازه اش O(r log r) است. آن را به simplex هایی با استفاده از روش بعد تجزیه می کنیم که به آن "bottom-vertex simplicial decomposition" می گویند.

منظور از تجزیه به simplex ها این است:

1) اجتماع آنها کل فضا را بدهد.

2) اشتراک دو به دوی آنها تهی باشد.

3) هر عضو از مجموعه صفحات منتخب با هر simplex انتخاب شده یا اشتراک تهی داشته باشد یا simplex زیرمجموعه آن باشد.

با استقرا روی تعداد ابعاد به دست می آید:

برای یک بعد خود arrangement جواب است. برای ابعاد بالاتر به ازای هر صفحه از مجموعه F می توانیم X|f و arrangement آن را در آن صفحه حساب کنیم. ...

* جستجوی تقاطع پاره خط ها

با point location و ساختمان داده مناسب می توان در O(n^(d+epsilon)) پیش پردازش (به ازای هر اپسیلون) و زمان کوئری O(log n) به آن جواب داد.

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

*جستجوی بازه ای

مساله simplex range searching : مجموعه P از n نقطه در صفحه اقلیدسی d بعدی داده شده است، می خواهیم P را طوری پیش پردازش کنیم و ساختمان داده ای بسازیم که به ازای simplex S کوئری d بعدی بتوانیم تعداد نقاطی از P را که در آن می افتند بشماریم. (یعنی اشتراک S و P)

با دوگان گرفتن حل می کنیم. یک simplex با d بعد را می توان به صورت تقاطع d+1 نیم ابرصفحه در نظر گرفت. حالا با دوگان گرفتن ابرصفحه به نقطه تبدیل می شود و مساله به مساله ی اول (مکان یابی نقطه) تبدیل می شود.

* جستجوی نزدیک ترین همسایه

مجموعه P از n نقطه در فضای اقلیدسی d بعدی داده شده، آن را طوری به صورت یک ساختمان داده پیش پردازش کنید که به ازای نقطه کوئری داده شده q نزدیک ترین نقطه به آن از بین نقاط P را بدهد.

argmin sqrt( sum_i_1_d(pi-qi)^2 )

(sqrt is monotone) ==> argmin sum_i_1_d (pi-qi)^2 = argmin sum_i_1_d (pi^2)-2sum(pi qi)+sum(qi^2)

(qi^2 is constant for all points: it's query point)

==> argmin (sum(pi^2)-2*sum(pi qi) )

f_p(x) = sum(pi^2) -2sum(pi xi)

این تابع یک ابرصفحه است. کوئری نزدیک ترین همسایه یک x برای تابع بالا می دهد و می خواهد نقطه ای که f_p(x) را مینیمم می کند پیدا کند. این معادل point location در دیاگرام کمینه سازی مجموعه همه ی fp ها است. (دیاگرام ورونوی)

همان کار قسمت اول را انجام می دهیم فقط به جای اینکه تجزیه را برای همه ی ناحیه ها انجام دهیم فقط برای ناحیه های زیر lower envelope انجام می دهیم.

زمان کوئری O(log n) و زمان پیش پردازش O(n^(ceil(d/2)+epsilon)) است.

فصل 2 هندسه پیشرفته vladlen

اپسیلون-نت و ابعاد VC

-اپسیلون نت

کاربرد در ساختارهای هندسی تصادفی

تابع X با احتمال m را در نظر بگیرید. اکثرا m یکنواخت است. یک مجموعه از زیرمجموعه X را F بنامید. (X,F) را یک سیستم مجموعه (set system) می نامند. (اگر X یک مجموعه متناهی باشد به آن ابرگراف هم می گویند.) یک اپسیلون-نت برای (X,F) مجموعه ای است که همه ی اعضای با m بیشتر از اپسیلون از مجموعه های F را شامل می شود.

مثال: یک set system متناهی (X,F) که در آن تعداد اعضای X برابر n است و تابع احتمال یکنواخت است (m(S) =|S|/n). یک 1/r-نت (برای r طبیعی مثبت) برای (X,F) زیرمجموعه N از X است که با همه ی اعضای F که حداقل n/r عضو دارند اشتراک ناتهی دارد.

اپسیلون-نت های کوچک برای ما جالب هستند. مخصوصا به ازای اپسیلون ثابت، می خواهیم یک اپسیلون-نت با اندازه ی ثابت پیدا کنیم! یعنی اندازه ی آن به اپسیلون وابسته باشد اما به set system وابسته نباشد. این همیشه ممکن نیست ولی معمولا ممکن است. برای توضیح کلاسی از ست سیستم ها نیاز به که اپسیلون-نت های کوچک دارند نیاز به تعریف VC-بعد داریم.

2.2. تعریف VC-بعد

VC-بعد یک پارامتر عددی برای ست سیستم است که نشان می دهد که سیستم چقدر خوش رفتار است. یک ست سیستم (X,F) و زیرمجموعه Y از X داده شده است محدود کردن F روی Y مجموعه ی F|y است که اشتراک مجموعه های F با مجموعه ی Y است.

تعریف: یک ست سیستم (X,F) و زیر مجموعه A از X  (تعریف بالا) را توسط F شکسته شده می نامیم اگر هر زیرمجموعه A اشتراک یک عضو F با A باشد؛ یعنی F|y = 2^A. بعد VC برای F بزرگترین زیرمجموعه از X است که با F شکسته می شود.

مثال: X را صفحه اقلیدسی (دو بعدی) و F1 را مجموعه همه ی چندضلعی های محدب در صفحه و F2 را مجموعه ی همه ی نیم صفحه ها فرض کنید. ست سیستم (X,F1) بعد VC بینهایت دارد. یک مجموعه A به دلخواه بزرگ از صفحه که محدب باشد در نظر بگیرید. هر عضو A' از A می تواند به صورت اشتراک A با یک چندضلعی محدب دیده شود.

اما ست سیستم (X,F2) تعداد بعد VC آن 3 است.

*تابع شکست

ماکسیمم تعداد اعضای F|y به ازای همه ی مجموعه های m عضوی از X را تابع شکست ست سیستم (X,F) به ازای m می نامند.

*اپسیلون نمونه

به ازای ست سیستم (X,F) ، یک زیرمجموعه N از X را اپسیلون نمونه برای (X,F) می نامیم اگر به ازای هر عضو F مثل S داشته باشیم: اختلاف نسبت اشتراک N و S به تعداد اعضای N و m(S) کمتر مساوی اپسیلون باشد.

*قضیه اپسیلون نمونه

به ازای ست سیستم (X,F) که dim(F) <= d که دی بزرگتر مساوی 2 و آر بزرگتر مساوی 2 که آر یک پارامتر است یک 1/r-نمونه برای (X,F) با اندازه ی حداکثر Cdr^2 ln r وجود دارد که C یک ثابت مطلق است.

فصل 1 هندسه پیشرفته vladlen

لینک فایل را قبلا گذاشته ام.

موضوعات فصل 1:

-ترکیب آفین و ترکیب محدب

تبدیل آفین sum(xi*ai) ها است که xi ها نقاط اند و ai ها ضریبهایی که جمع آنها 1 می شود.

ترکیب محدب ترکیبی است که در آن ai ها مثبت باشند. (در نتیجه هر کدام از 1 هم کمتر می شوند.)

وابستگی آفین: اگر یک نقطه را بتوان به صورت ترکیب آفین بقیه نوشت.

زیرفضای خطی: k-flat گذرنده از مبدا

-قضیه رادون (Radon)

یک مجموعه با d+2 نقطه را می شود به دو مجموعه افراز کرد که پوسته ی محدب آنها اشتراک نداشته باشد. (فضا d بعدی)

اثبات: وابستگی آفین

-قضیه هلی (Helly)

اگر n مجموعه محدب داشته باشیم که هر d+1 تای آنها متقاطع اند، همه ی آنها متقاطع اند.

اثبات: قضیه رادون

-قضیه Caratheodory

هر ترکیب محدب n نقطه یک ترکیب محدب از حداکثر d+1 نقطه از بین آنهاست. (در فضای d بعدی)

اثبات: وابستگی آفین و وابستگی محدب

زوج نقاط خوب جدا شده (WSPD)

تجزیه نقاط به زوج نقاط خوب جدا شده:

الگوریتم به دست آوردن پوشاننده (spanner) با WSPD:

زمان و حافظه ی الگوریتم های پوشاننده ها:

پوشاننده های هندسی

اسلاید آن را قبلا گذاشته بودم. (اسلاید دانشگاه یزد بود).

الگوریتم حریصانه ی اصلی جواب بهینه را حساب می کند اما دومی که زمان کمتری می برد O(n^2 log n) جواب بهینه را حتی برای حالت متریک حساب نمی کند.

به جای این کار می خواهیم به صورت زیر عمل کنیم:

تتا-گراف:

انواع تتا گراف:

تتا گراف پوشای سینک:

تتاگرافی است که درجه ی آن محدود است.

پوشاننده ی لیست پرشی:

تتاگرافی که قطر آن از مرتبه لگاریتم تعداد راسهاست.

زمان آن O(n log n) است و حافظه O(n) است.