http://ce.sharif.edu/~fazli/papers/fazli-joco2015.pdf
http://theory.epfl.ch/osven/courses/Approx13/
مزیتش نسبت به بقیه‌ی درس‌های ارائه شده تأکیدی است که روی رند کردن دارد.
https://arxiv.org/pdf/1612.07925.pdf
این یکی از مواردی بود که در سمینار زمستانی ارائه شد.
ایده‌اش این بود که از اقلیدسی بودن فضا استفاده کرده بود و حالت‌بندی کرده بود که اگر فاصله‌ی این نقطه‌ها بیشتر از یک حدی بود مثلاً هر دو تا مرکز را باز می‌کنم و در غیر این صورت فقط یکی را. توضیحش هم این بود که ارزش مرکزها را میزان گزینه‌های ممکن تعیین می‌کند و اینکه همین‌طوری اگر همه را باز کنیم یا یک maximal independent set باز کنیم کافی نیست چون فقط داریم حالتی که دو بار یک مرکز باز شود را حذف می‌کنیم.
یک روش رندکردن هم داشت که می‌گفت با نرخ نمایی کم می‌کند تا تعداد مرکزها را به k تا برساند. می‌گفت پیوسته اگر بخواهیم این را کم کنیم نمایی طول می‌کشد و ما پرش‌هایی تعریف می‌کنیم که چندجمله‌ای بشود. (coarse geometric bucketing)
سوالهای حل‌نشده:
- کران پایین
- بهبود زمان اینها
- سختی تقریب برای حالت گسسته
به طور ویژه پرسیده بود می‌شود کاری کرد که مرکزهای الگوریتم LMP را به k رساند؟
اینجا هدف این است که از ابعاد بالاتر فضای اقلیدسی یک گراف را به فضای با ابعاد کمتر بیاورد که تقریب فاصله‌ها زیاد نشود. در مجموع با دو روش دیگری که گفته برای سایر متریک‌ها هم معلوم است که چه اتفاقی می‌افتد.
http://www.cs.cmu.edu/~anupamg/adfocs/adfocs3.pdf
