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 رساند؟