Map Labeling Problem

(من به طرز عجیبی همیشه این صفحه‌ها را جا می‌انداختم توی جزوه و بار اول است دارم می‌خوانمشان!!)

نسخه ۱: ماکسیمم کردن طول ضلع

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

جواب: مسأله NP-hard است و تقریب ۲ دارد و ثابت شده بهتر از آن نمی‌شود.

نسخه ۲: ماکسیمم کردن تعداد مربع‌ها

می‌خواهیم k مربع مجزا داشته باشیم که یک رأس هر کدام از مجموعه نقاط باشد و k ماکسیمم باشد. (در نتیجه یک سری نقاط یک رأس مربع نخواهند بود.)

*دوگان؟

من در جزوه نوشتم که این دو مسأله دوگان هم هستند.

*گراف تقاطع: هر شئ یک رأس است و اگر همدیگر را قطع کنند یک یال بین آنها می‌کشیم.

*نسخه ۲: بیان دیگر آن با گراف تقاطع به این صورت است که بزرگترین زیرمجموعه مستقل در گراف تقاطع مربع‌های با ضلع یکسان با یک رأس از نقاط ورودی

*در گرافهای کلی:

مسأله NP-hard است و تقریب با ضریب بهتر از n^(1-delta) ندارد که به ازای این مسأله مثلاً به جای n مربع یک مربع می‌دهد که در نتیجه یک مربع را هم بدهیم به این ضریب تقریب می‌رسیم.

گراف تقاطع با گراف معمولی فرق دارد (مثال: ستاره ۶ رأسی گراف تقاطع نیست.). فعلاً حالت‌های خاص را بررسی می‌کنیم.

مسأله قبل را به صورت اینکه یک سری مربع داریم و می‌خواهیم آنها را شیفت بدهیم تا یک رأس آنها یکی از نقاط ورودی باشد هم تعریف می‌کنند.

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

*الگوریتم تقریبی برای حالتی که نقاط زیرمجموعه‌ای از رأسهای یک توری باشند.

برای این کار L نوار عمودی توری متوالی را با هم در یک دسته می‌گذاریم و جواب بهینه‌ی هر دسته را به دست می‌آوریم که برای کل مسأله هم یک جواب تقریبی است. انجام این کار (تقسیم به L نوار عمودی) به L حالت ممکن است که به صورت تصادفی یکی از اینها را انتخاب می‌کنیم.

تحلیل:

جواب بهینه را در نظر بگیرید. ما در آن همه‌ی مربع‌هایی که خطوط توری را قطع می‌کرده‌اند حذف کرده‌ایم. حداکثر تعداد این مربع‌ها در هر خانه m^2 تا است (m=ضلع خانه‌ی توری) که در کل حداکثر O(n^m^2) می‌شود. (؟)