How to Write a Proof

https://www.microsoft.com/en-us/research/wp-content/uploads/2016/12/How-to-Write-a-Proof.pdf

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

مجموعه‌ی هسته‌ی اپسیلون-تقریب برای پوسته محدب بدون وابستگی به تعداد ابعاد

http://arxiv.org/pdf/1507.02574.pdf

اگر اشتباه نکنم این پیشنهاد اولیه دکتر ضرابی‌زاده برای پروژه‌ی من بود. :)) خدا رحم کرده بهم.

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

Streaming Algorithms for Estimating the Matching Size in Planar Graphs and Beyond

http://epubs.siam.org/doi/abs/10.1137/1.9781611973730.81

Parameterized Streaming Algorithms for Vertex Cover

http://arxiv.org/pdf/1405.0093.pdf

پیمایش گراف‌های نامتناهی با جهت‌گیری‌های محلی تصادفی

http://arxiv.org/pdf/1308.1041.pdf

چطور یک ربات با حافظه محدود یک گراف نامحدود را طی می‌کند؟

http://dwhite03.web.wesleyan.edu/files/Lecture%20Notes/compGraph%20Theory%20CS%20Talk.pdf

فرار مستطیل‌ها

http://www-scf.usc.edu/~emamjome/publications/2013-CCCG.pdf

Formann 91 Map Labeling

این قسمت سر کلاس درس داده نشد اما جالب بود به همین دلیل اینجا می‌نویسم.

با توجه به شرط‌های موازی بودن با محورهای مختصات و داشتن یک رأس روی نقاط ورودی، به ازای هر نقطه ۴ مستطیل ممکن داریم.

در حالت کلی گفتیم که مسأله NP-hard است اما اگر اجازه دهیم دو مستطیل از مستطیل‌ها مجاز باشند حل می‌شود.

یکی از این دو حالت مجاز را با xi و دیگری را با xi' نشان می‌دهیم (برای هر نقطه pi). در نتیجه تقاطع دو مستطیل به صورت یک عبارت با دو جمله نشان داده می‌شود. پس به مسأله‌ی 2-SAT تبدیل می‌شود و در زمان خطی از مرتبه تعداد تقاطع‌های مستطیل‌ها حل می‌شود.

لم ۱: اگر مستطیلی بیشتر از ۲۴ مستطیل دیگر را قطع کند جواب نداریم.

نتیجه: تعداد تقاطع مستطیل‌ها ثابت است پس از مرتبه O(n^2) تقاطع داریم. (انتخاب دو مستطیل متقاطع * ۲۴) که این حالت می‌تواند اتفاق بیفتد:

اگر تعداد تقاطع‌های مستطیل‌ها p تا باشد، می‌توان در زمان O(n log n + p) آنها را پیدا کرد و حالت جواب نداشتن را تشخیص داد.

برای این مسأله الگوریتم O(n log^2 n) ارائه شده است و برای حالت خاص آن که مربع‌های هم‌اندازه باشد الگوریتم O(n lg n) وجود دارد.

*الگوریتم برای حالت کلی:

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

*تحلیل:

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

لم: تعداد مربع‌هایی که نقطه‌ای در آنها نیست و مربع حول یک نقطه را قطع می‌کنند حداکثر ۲ است.

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

با توجه به اینکه حداکثر ۲ مربع حول یک نقطه می‌توانند شامل نقطه باشند و لم قبل ثابت می‌شود.

زمان اجرا: در حالت عادی باید O(n^2) شود اما با استفاده از یک sweep که O(n log n) زمان می‌برد و محاسبه‌ی جواب 2-SAT در هر گام که O(n) زمان می‌برد، اگر جوابها را تا پایان رویدادها حساب کنیم و بعداً با باینری سرچ جواب بهینه را پیدا کنیم، می‌توانیم زمان کل الگوریتم را به O(n lg n) برسانیم.

*تعمیم:

با یک تبدیل آفین می‌توان آن را به حالت‌های دیگر هم تعمیم داد.

*اثبات NP-complete بودن:

مسأله‌ی 3-SAT را به این مسأله تبدیل می‌کنیم. نقاط را طوری می‌چینیم که فقط دو مستطیل مجاز داشته باشند که به این حالت‌ها xi و x'i می‌گوییم. در نتیجه برای نقاط مجاور آنها هم جواب به صورت یکتا معلوم می‌شود که به آن هم یک متغیر نسبت می‌دهیم. در نتیجه به ازای هر نقطه متغیر دو قطر و متغیر مستطیل‌های خود آن را باید در نظر بگیریم که در کل ۳ تا متغیر می‌شود. پس اینکه تصمیم بگیریم که n نقطه را می‌توان با مستطیل‌ها پوشاند NP-complete است.

Improved Approximation Algorithms for Label Cover Problems

https://www.cs.princeton.edu/~moses/papers/LabelCover.pdf