مسئله پوشش بیشینه

مسئله پوشش بیشینه (به انگلیسی: maximum coverage problem)، یک سؤال کلاسیک در علوم رایانه و نظریه پیچیدگی محاسباتی است. این مسئله به طور گسترده در الگوریتم‌های تقریبی آموزش داده می‌شود. برای ورودی تعدادی مجموعه و یک عدد $k$ داده می‌شود. مجموعه‌ها می‌توانند عضو مشترک داشته باشند. شما باید به تعداد حداکثر $k$ تا از این مجموعه‌ها را انتخاب کنید به طوری که حداکثر تعداد اعضا پوشش داده شود؛ برای مثال اجتماع مجموعه‌های انتخاب شده، بیشینه تعداد اعضا را دارد. به عبارت دیگر، پوشش بیشینه (بدون وزن) نمونه: عدد $k$ و مجموعه‌ای از مجموعه‌ها $S=S_{1},S_{2},\ldots ,S_{m}$. هدف: یافتن یک زیرمجموعهٔ $S^{'}\subseteq S$ ، به طوری که $\left|S^{'}\right|\leq k$ و تعداد اعضای پوشانده شده $\left|\bigcup _{S_{i}\in S^{'}}{S_{i}}\right|$ حداکثر باشد. مسئله پوشش بیشینه یک ان‌پی سخت (به انگلیسی: NP-hard) و نمی‌تواند تحت مفروضات استاندارد با $1-{\frac {1}{e}}+o(1)\approx 0.632$ تقریب زده شود. این نتیجه در اصل با نسبت تقریبی الگوریتم حریصانه عمومی که برای بیشینه‌سازی توابع زیرپیمان‌های با محدودیت کاردینالیتی (به انگلیسی: maximization of submodular functions with a cardinality constraint) به کار می‌رود، مطابقت دارد.

صورتبندی به شکل برنامه خطی عدد صحیح

مسئله پوشش بیشینه می‌تواند به شکل زیر در قالب برنامه‌ریزی خطی عدد صحیح (به انگلیسی: Integer Linear Program) فرمول‌بندی شود.

بیشینه‌سازی $\sum _{e_{j}\in E}y_{j}$. (بیشینه‌سازی مجموع اعضای پوشش داده شده).

با توجه به اینکه $\sum {x_{i}}\leq k$؛ (تعداد مجموعه‌های انتخاب شده بیشتر از نیست).

$\sum _{\,e_{j}\in S_{i}}x_{i}\geq y_{j}$؛ (اگر $y_{j}\geq 0$ آنگاه حداقل یک مجموعهٔ $e_{j}\in S_{i}$ انتخاب شده است).

$0\leq y_{j}\leq 1$؛ (اگر$y_{j}=1$ آنگاه $e_{j}$ پوشش داده شده است)

$x_{i}\in \{0,1\}$ (اگر $x_{i}=1$ آنگاه $S_{i}$ برای پوشش دادن انتخاب شده است).

الگوریتم حریصانه

الگوریتم حریصانه برای پوشش بیشینه، مجموعه‌ها را بر اساس یک قاعده انتخاب می‌کند: در هر مرحله، مجموعه‌ای را انتخاب کن که شامل بیشترین تعداد اعضای پوشش داده نشده باشد. می‌توان نشان داد که این الگوریتم به نسبت تقریب $1-{\frac {1}{e}}$ می‌رسد. نتایج نشان می‌دهد که الگوریتم حریصانه، بهترین الگوریتم تقریب زمانی چند جمله‌ای ممکن برای پوشش بیشینه است.

تعمیم‌های شناخته شده

نتایج غیرتقریبی به همهٔ تعمیم‌های مسئله پوشش بیشینه اعمال می‌شود زیرا آنها مسئله پوشش بیشینه را به عنوان یک حالت خاص دارند.

حالت وزن دار

در مدل وزن دار هر عضو $e_{j}$ وزنی برابر $w(e_{j})$ دارد. هدف یافتن یک پوشش بیشینه است به طوری که بیشترین وزن را داشته باشد. حالت پایه، حالت خاصی است که همه وزن‌ها برابر $1$ است.

بیشینه‌سازی $\sum _{e\in E}w(e_{j})\cdot y_{j}$. (بیشینه‌سازی مجموع وزندار اعضای پوشش داده شده).

با توجه به اینکه$\sum {x_{i}}\leq k$ ؛ (تعداد مجموعه‌های انتخاب شده بیشتر از $k$ نیست).

$\sum _{e_{j}\in S_{i}}x_{i}\geq y_{j}$ ؛ (اگر $y_{j}\geq 0$ آنگاه حداقل یک مجموعهٔ $e_{j}\in S_{i}$ انتخاب شده است).

$0\leq y_{j}\leq 1$ ؛ (اگر $y_{j}=1$ آنگاه $e_{j}$ پوشش داده شده است).

$x_{i}\in \{0,1\}$ (اگر $x_{i}=1$ آنگاه $S_{i}$ برای پوشش دادن انتخاب شده است).

الگوریتم حریصانه برای پوشش بیشینه وزندار در هر مرحله مجموعه‌ای را انتخاب می‌کند که دارای بیشترین وزن اعضای پوشش داده نشده باشد. این الگوریتم به نسبت تقریب $1-{\frac {1}{e}}$ می‌رسد.

پوشش بیشینه بودجه‌ای

در حالت پوشش بیشینه بودجه‌ای (به انگلیسی: Budgeted maximum coverage)، نه تنها هر عضو $e_{j}$ وزنی برابر $w(e_{j})$ دارد، بلکه هر مجموعه $S_{i}$ قیمتی برابر $c(S_{i})$ دارد. به جای $k$ که تعداد مجموعه‌ها در پوشش را محدود می‌کند، بودجهٔ $B$ داده می‌شود. بودجهی $B$ وزن پوششی که می‌تواند انتخاب شود را محدود می‌کند.

بیشینه کردن $\sum _{e\in E}w(e_{j})\cdot y_{j}$ . (بیشینه کردن مجموع وزندار اعضای پوشش داده شده).

با توجه به اینکه $\sum {c(S_{i})\cdot x_{i}}\leq B$ ؛ (هزینه مجموعه‌های انتخاب شده از بیشتر نیست).

$\sum _{e_{j}\in S_{i}}x_{i}\geq y_{j}$ ؛ (اگر $y_{j}\geq 0$ آنگاه حداقل یک مجموعهٔ $e_{j}\in S_{i}$ انتخاب شده است).

$0\leq y_{j}\leq 1$ ؛ (اگر $y_{j}=1$ آنگاه $e_{j}$ پوشش داده شده است).

$x_{i}\in \{0,1\}$ (اگر $x_{i}=1$ آنگاه $S_{i}$ برای پوشش دادن انتخاب شده است).

الگوریتم حریصانه دیگر راه حل‌هایی با تضمین کارایی ارائه نخواهد کرد. یعنی ممکن است رفتار این الگوریتم در بدترین حالت با راه حل بهینه بسیار متفاوت باشد. الگوریتم تقریب به روش زیر بدست می‌آید. ابتدا، پس از یافتن راه حلی که از الگوریتم حریصانه استفاده می‌کند، راه حل بهتر الگوریتم حریصانه و مجموعه با بیشترین وزن را بازمی‌گردانیم. این روش را، الگوریتم حریصانه اصلاح شده می‌نامیم. در مرحله دوم، با شروع از همهٔ خانواده‌های ممکن مجموعه‌های اندازه‌ها از یک تا (حداقل) سه، این راه حل‌ها را با الگوریتم حریصانه اصلاح شده تقویت می‌کنیم. در مرحله سوم، بهترین راه حل تقویت شده را بازمی‌گردانیم. این الگوریتم به نسبت تقریب $1-1/e$ می‌رسد. این بهترین نسبت تقریب ممکن است مگر $NP\subseteq DTIME(n^{O(\log \log n)})$.

پوشش بیشینه تعمیم یافته

در تعمیم یافتهٔ پوشش بیشینه هر مجموعهٔ $S_{i}$ قیمت $c(S_{i})$ دارد، عضو $e_{j}$ دارای وزنی متفاوت و هزینه‌ای بسته به مجموعه‌ای که آن را پوشش می‌دهد، دارد. یعنی اگر $e_{j}$ توسط مجموعهٔ $S_{i}$ پوشش داده شده باشد، وزن $e_{j}$ برابر $w_{i}(e_{j})$ و هزینهٔ آن برابر $c_{i}(e_{j})$ خواهد بود. بودجه $B$ برای هزینهٔ کل راه حل داده شده است.

بیشینه کردن $\sum _{e\in E,S_{i}}w_{i}(e_{j})\cdot y_{ij}$ . (بیشینه کردن مجموع وزندار اعضای پوشش داده شده در مجموعه‌هایی که پوشش داده شده‌اند).

با توجه به اینکه $\sum {c_{i}(e_{j})\cdot y_{ij}}+\sum {c(S_{i})\cdot x_{i}}\leq B$ ؛ (هزینهٔ مجموعه‌های انتخاب شده نباید بیشتر از $B$ باشد).

$\sum _{i}y_{ij}\leq 1$ ؛ (عضو $e_{j}=1$ می‌تواند حداکثر با یک مجموعه پوشش داده شود).

$\sum _{S_{i}}x_{i}\geq y_{ij}$ ؛ (اگر $y_{j}\geq 0$ آنگاه حداقل یک مجموعهٔ $e_{j}\in S_{i}$ انتخاب شده است).

$y_{ij}\in \{0,1\}$ ؛ (اگر $y_{ij}=1$ آنگاه $e_{j}$ توسط مجموعه‌ی' $S_{i}$ پوشش داده شده است).

$x_{i}\in \{0,1\}$ (اگر $x_{i}=1$ آنگاه $S_{i}$ برای پوشش دادن انتخاب شده است).

الگوریتم پوشش بیشینه تعمیم یافته

این الگوریتم از مفهوم باقیماندهٔ وزن/هزینه استفاده می‌کند. باقیماندهٔ وزن/هزینه در مقابل یک راه حل آزمایشی اندازه‌گیری می‌شود و این تفاوت بین وزن/هزینه و وزن/هزینه بدست آمده با یک راه حل آزمایشی است. این الگوریتم چندین مرحله دارد. اول، یافتن راه حلی که از الگوریتم حریصانه استفاده می‌کند. در هر تکرار الگوریتم حریصانه، راه حل آزمایشی مجموعه‌ای را که شامل بیشترین مقدار وزن اعضای باقیمانده تقسیم بر هزینهٔ این اعضا همراه با هزینه اعضای باقیمانده دارد، اضافه می‌کند. دوم، مقایسهٔ راه حل بدست آمده در قدم اول با راه حل بهینه که از تعداد کمی از مجموعه‌ها استفاده می‌کند. سوم، بازگرداندن بهترین راه حل از بین راه حل‌های بررسی شده. این الگوریتم به نسبت تقریب $1-1/e-o(1)$ می‌رسد.

مسائل مرتبط

• مسئله پوشش مجموعه مسئله‌ای برای پوشش همه عناصر با کمترین مجموعه‌های ممکن است.

منابع

• Vazirani, Vijay V. (2001). Approximation Algorithms. Springer-Verlag. ISBN 3-540-65367-8.
• Uriel Feige, A Threshold of ln $n$ for Approximating Set Cover, Journal of the ACM (JACM), v.45 n.4, p. 634 - 652, July 1998.