تقریب با دو پارامتر

اگر Y یک الگوریتم (a,b)-تقریبی برای X باشد یعنی

X <= Y <= a.X+b

استفاده از تجانس برای پیدا کردن نزدیک ترین همسایه در ابعاد بالا

http://aidblab.cse.iitm.ac.in/cs625/6.FastMap.pdf

البته این کار را با روش دیگری امتحان کرده است، شاید با روشی که من می خواهم انجام بدهم کار کند.

یادآوری

به من یادآوری کنید که به استادم یادآوری کنم که به بچه ها یادآوری کنند که سر ارائه ی من بیایند.

به نظرم قسمت های زیادی از موضوع را اشتباه فهمیدم و هر چه بیشتر می خوانم بیشتر گیج می شوم و کمتر می فهمم.

min-wise independent hashing

http://www.cs.princeton.edu/courses/archive/spr04/cos598B/bib/BroderCFM-minwise.pdf

ارائه خودم (به زودی!)

قرار بود در مورد LSH ارائه بدهم، سری قبل انقدر نمره کم گرفته بودم که اصلا دلم نمی خواد برم ارائه بدم حتی! ترجیح می دهم همینجا بگذارمش.

دریافت
حجم: 1.22 مگابایت

ساختارهای کوئری هندسی تقریبی

مرجع: http://www.ics.uci.edu/~goodrich/pubs/crc-chap05.pdf

پروژه هندسه محاسباتی پیشرفته

دریافت
حجم: 193 کیلوبایت

هنوز با این لاتکس؟ فارسی درگیری دارم. تازه هر نسخه ای از نرم افزارهاش هم با اون یکی فرق داره.

باید ارائه ی این را هم آماده کنم. (این داستان ادامه دارد..)

نزدیک ترین همسایه در ابعاد بالا

روش locality sensitive hasing

MIT

Piotr Indyk

Slides

ویکیپدیا

Stanford

(آدرس سایت اصلی الگوریتم های هندسی تقریبی http://graphics.stanford.edu/courses/cs468-06-fall/)

الگوریتم های بهینه برای خوشه بندی تقریبی

فاصله درون خوشه ای:

1- حداکثر فاصله بین نقاط درون یک خوشه (فاصله زوج نقاط: بدون مرکز)

2- حداکثر فاصله بین نقاط درون یک خوشه و مرکز خوشه (دارای مرکز)

الگوریتمی که ضریب تقریب بهتری از 2 داشته باشد برای ابعاد 2 و بالاتر وجود ندارد مگر اینکه P=NP باشد. الگوریتم با زمان O(nlogk) داریم که طبق algebraic decision tree بهینه است. اگر (حداکثر) اندازه ی خوشه مشخص باشد تعداد خوشه ها را با تقریب 1+epsilon خواهیم داشت.

از گونه های دیگر مساله مرکزهای ممنوعه، مساله تامین کنندگان و مساله تامین کنندگان وزن دار است که با زمان O(nlogk) به جواب بهینه یا نزدیک بهینه تقریبی می رسند.

پوشش راسی

دریافت
عنوان: vertex cover
حجم: 113 کیلوبایت