broadcast در شبکه بیسیم وایرلس

می‌خواهیم پیامی را از یک پردازنده به بقیه برسانیم و حداقل تعداد ارسالها را داشته باشیم.

اطلاعات کامل را داشته باشیم: مجموعه‌ی رأسهایی که ارسال می‌کنند باید همبند باشد و باید یک پوشش رأسی برای گراف باشند.

این مسأله np-hard است.

تقریب مسأله با فرض داشتن اطلاعات محلی: اگر هر گره همسایه‌های خودش را بداند (شعاع ارسال ثابت باشد) می‌توان الگوریتمی با تقریب ثابت برای مسأله ارائه داد.

الگوریتم: هر گره مختصات خودش و همسایه‌هایش را دارد. پس چون رأسی که از آن پیام را دریافت کرده است حتما در همسایگی‌اش است مختصات آن را هم دارد و می‌تواند حساب کند که آیا نقاطی که در همسایگی‌اش هستند قبلاً پیام را دریافت کرده‌اند یا خیر و فقط در صورتی بفرستد که بداند آن نقطه از جای دیگری پیام را دریافت نکرده است یا در حال دریافت آن نیست.

ایراد: ممکن است یک نفر دو بار پیام دریافت کند و این کار ممکن است باعث تداخل و نامفهوم شدن پیام شود.

Truth, Justice and Cake Cutting

http://www.eecs.harvard.edu/econcs/pubs/Chen10.pdf

ارائه‌ی فردای جلسه‌ی الگوریتم. خوشمزه به نظر می‌رسه! ( این یکی از مسأله‌هاییه که هر دفعه می‌بینمش خوشحال میشم! :) )

Imagine a cake that must be divided between a group of gluttonous children. To complicate

matters, the cake is heterogeneous: two pieces of cake may differ in terms of their toppings, so

the children have different preferences over the pieces (one may weakly prefer a larger proportion

of chocolate curls, while another may single-mindedly desire the piece with the cherry).

In this lecture we discuss the surprisingly intricate problem of fairly dividing the cake — which

serves as a metaphor for heterogeneous divisible resources such as land or time.

From a computer scientist’s point of view, the cake cutting problem provides a sandbox in which

we can explore the role of computational thinking in the allocation of divisible goods. Indeed, the

elegant cake cutting model distills many of the issues we care about when studying divisible

goods more broadly; for example, how to reason about computational complexity in the face of

continuous inputs, and how to quantify the tradeoffs between individual fairness and global

welfare.

Fast Computation of Output-Sensitive Maxima in a Word RAM

http://www.madalgo.au.dk/~peyman/pubdata/maxima.soda14.pdf

algebraic decision tree

اگر با یک تابع چندجمله‌ای جدا کنیم به آن algebraic decision tree می‌گویند. حالت خاص آن درخت تصمیم معمولی است که بر مبنای مقایسه تقسیم می‌کند. حالت خطی linear decision tree با تابع خطی جدا می‌کند.

مرجع: http://en.wikipedia.org/wiki/Algebraic_decision_tree

online auctions

http://www.cs.umd.edu/~hajiagha/AGT10/13-10-10-OnlineAuctions.pdf

پردازش زبان طبیعی بر مبنای گراف برای استخراج داده

الگوریتم قدم زدن تصادفی زاویه‌ای

بالاخره چیزی که می‌خواستم پیدا کردم:

که وقتی ربات آن را اجرا می‌کند نتیجه این می‌شود:

Gap Navigation Tree

http://msl.cs.uiuc.edu/~lavalle/papers/TovMurLav07.pdf

http://en.wikipedia.org/wiki/Motion_planning

http://en.wikipedia.org/wiki/Any-angle_path_planning

برنامه ریزی حرکت ربات

ویکیپدیا:

http://en.wikipedia.org/wiki/Motion_planning

الگوریتم‌ها:

http://www.mpi-inf.mpg.de/departments/d1/teaching/ss10/Seminar_CGGC/Slides/06_Bazhenova_RMP.pdf

GNT:

http://www.robotoloco.com/wk/papers/TovGuiLav04.pdf

Terrain Visibility with Multiple Viewpoint

http://arxiv.org/pdf/1309.4323v1.pdf