Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms

https://arxiv.org/pdf/1612.07925.pdf

این یکی از مواردی بود که در سمینار زمستانی ارائه شد.

ایده‌اش این بود که از اقلیدسی بودن فضا استفاده کرده بود و حالت‌بندی کرده بود که اگر فاصله‌ی این نقطه‌ها بیشتر از یک حدی بود مثلاً هر دو تا مرکز را باز می‌کنم و در غیر این صورت فقط یکی را. توضیحش هم این بود که ارزش مرکزها را میزان گزینه‌های ممکن تعیین می‌کند و اینکه همین‌طوری اگر همه را باز کنیم یا یک maximal independent set باز کنیم کافی نیست چون فقط داریم حالتی که دو بار یک مرکز باز شود را حذف می‌کنیم.

یک روش رندکردن هم داشت که می‌گفت با نرخ نمایی کم می‌کند تا تعداد مرکزها را به k تا برساند. می‌گفت پیوسته اگر بخواهیم این را کم کنیم نمایی طول می‌کشد و ما پرش‌هایی تعریف می‌کنیم که چندجمله‌ای بشود. (coarse geometric bucketing)

سوالهای حل‌نشده:

- کران پایین

- بهبود زمان اینها

- سختی تقریب برای حالت گسسته

به طور ویژه پرسیده بود می‌شود کاری کرد که مرکزهای الگوریتم LMP را به k رساند؟

ایده‌ی ارائه‌های امروز الگوریتم تقریبی

ایده‌ای که از همه جالب‌تر بود این است که یک تابع کران برای الگوریتم به دست می‌آوریم. بعد بر اساس توانهای اپسیلون (یا ضریب تقریب دیگر) آن را بازه‌بندی می‌کنیم. این کار باعث می‌شود خطای جمعی ما ضریب اپسیلون باشد. در نتیجه‌ی این کار جوابی که به دست می‌آید به دلیل اینکه از تابع کران استفاده کردیم تقریب مورد نظر ما خواهد بود.

ایده‌ی دیگری که دیدم این بود که فضای مسأله را بر اساس هزینه‌ی آن به صورت یک چندوجهی صعودی/نزولی اکید ذخیره می‌کردند. حتی به صورت ساختمان داده مربوط به آن مسأله خاص.

چیز جدید دیگری که دیدم این بود که نامساوی مثلث را برای یک semidefinite programming به صورت برداری نوشته بودند:

(vi-vj)(vi-vk) >= 0

که هیچ ایده‌ای ندارم چه ربطی به نامساوی مثلث دارد؟

بدون شرح!

http://www.informatik.uni-trier.de/~ley/pers/hd/a/Abam:Mohammad_Ali

A Webpage on The Erdos Distance Problem by William Gasarch

https://www.cs.umd.edu/~gasarch/erdos_dist/erdos_dist.html

word ram model of computation

http://courses.csail.mit.edu/6.851/spring07/scribe/lec12.pdf

استراتژی‌های حل مسأله

دیدم کتابش را برداشتم گفتم حالا چند مورد را از روی کتاب بگویم اتفاقی نمی‌افتد... :) این‌ها بیشتر قسمت‌هایی است که خودم دوست داشتم! :)

نزول نامتناهی: ایده مربوط به زمان فیثاغورث است که میگه اگر فرض کنیم یک مسأله در اعداد طبیعی جواب داشته باشه و از روی این جواب بشه نتیجه گرفت برای اعداد کوچکتری هم مسأله در اعداد طبیعی جواب دارد یعنی کلاً جواب ندارد چون اعداد طبیعی از پائین کران‌دار اند! :) یک جوری مثل شهود استقرا توی یه حالت خاصه ولی فکر کنم اون موقع هنوز استقرا نیومده بوده! :)

ناوردایی: مسأله مشخصاتی داره که با یک عمل ثابت می‌مونه. برای حل مسأله دو جور میشه از این استفاده کرد یکی اینکه بگیم ویژگی توی حالت‌های مجاز مسأله هست که توی حالت جواب نیست پس هیچ وقت به جواب نمی‌رسه. حالت دیگه اینه که بگیم مثلاً رشد تابع هدف مسأله ثابته. اگر مسأله هدفش یک تابع صعودی /نزولی باشه یعنی هر بار مقدارش زیاد/کم بشه. مثلاً تابع هدف میتونه تعداد حالت‌های مسأله باشه که محدوده یا هزینه‌ی مسأله باشه که کرانداره چون همه‌اش داره کم/زیاد میشه حداکثر به اندازه‌ی تعداد حالت‌ها (کران) تقسیم بر تغییری که هر بار میکنه تکرار برای رسیدن به جواب لازمه.

http://en.wikipedia.org/wiki/Invariant_(mathematics)

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

رنگ‌آمیزی: من قبلاً با این مسأله حل کردم توی همین وبلاگ ولی اشاره به اسمش نکردم. یک سری ویژگی توی مسأله هستند که هر کدام را با یک رنگ مشخص می‌کنیم و بعد وقتی مسأله را حل می‌کنیم می‌توانیم با نگه داشتن هزینه‌ی هر کدام از رنگ‌ها (ویژگی‌ها) بدانیم اوضاع چطوریه! :) این را با اسم پارامتر ثابت می‌شناسند که هر کدام از رنگ‌ها یک پارامتر اند و تعداد اشیای هر رنگ مقدار آن پارامتر است.

*حالا اینها شاید خیلی هم درست نباشن و ادامه هم می‌دونم دارن ولی حالا دیگه این چیزی بود که من بلد بودم.

حل مسائل الگوریتمی با ماتریس

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

زنجیره مارکوف

simplex

حل رابطه بازگشتی با ماتریس (مثل فیبوناچی، فکر کنم قبلاً توضیح دادم.)

نظریه بازی‌ها: مثال در لینک زیر!

http://mathworld.wolfram.com/LightsOutPuzzle.html

یک پروژه‌ی پردازش تصویر هم داشتیم.

بقیه‌اش هم یادم نمیاد! :)

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

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

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

درس Motion Planning in Real and Virtual Worlds

سایت درس:

http://gamma.cs.unc.edu/courses/planning-f07/

مرجع درس: LaValle's Book on Planning Algorithms

دانلود کتاب درس و ...

http://planning.cs.uiuc.edu/

ارائه‌ی مورد علاقه‌ی من: Visibility based Motion Planning (Georgi Tsankov , October 10, 2007)

Coverage Planning (Jamie Snape, October 15, 2007)

تعمیم توری شش وجهی و EJ Networks (موازی)

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