دانلود مقاله یک روش پایین به بالا و الگوریتم های سریع برای مجموعه مستقل ماکسیمم
چکیده
در مقاله، ابتدا روش جدیدی به نام «روش پایین به بالا» را ارائه می‌دهیم که به طور غیر رسمی، بهبودی از پیچیدگی بدترین حالت برای نمونه‌های «پراکنده» به نمونه‌های «متراکم‌تر» را منتشر می‌کند و کاربردی ساده و در عین حال غیر بدیهی از آن را در مساله پوشش مجموعه مینیمم نشان می‌دهیم. سپس به مجموعه مستقل ماکسیمم می‌پردازیم. با پیروی از روش پایین به بالا، بهبودهای پیچیدگی بدترین حالت از گراف‌های با متوسط درجه d را در گراف‌های با متوسط درجه بالاتر از d منتشر می‌کنیم. در واقع، با استفاده از الگوریتم‌های برای مجموعه مستقل ماکسیمم در گراف‌های با درجه متوسط ۳، به بررسی مجموعه مستقل ماکسیمم در گراف‌های با درجه متوسط ۴، ۵ و ۶ می‌پردازیم. سپس تکنیک پایین به بالا را با تکنیک‌های معیارها و تسخیر به منظور بهبود زمان‌های اجرای گراف‌های با ماکسیمم درجه ۴، ۵ و ۶ و همچنین گراف‌های کلی ترکیب می‌کنیم. بهترین کرام‌های محاسباتی به دست آمده برای مجموعه مستقل ماکسیمم عبارتنداز: O∗(1.1571n), O∗(1.1918n) و O∗(1.2071n), برای گراف‌های با ماکسیمم درجه (یا با متوسط درجه کلی‌تر) به ترتیب ۴، ۵ و ۶، و O∗(1.2127n) برای گراف‌های عمومی. این نتایج بر اساس بهترین نتایج شناخته شده فضای چند جمله‌ای برای این موارد بهبود می‌یابند.
1. مقدمه
به تازگی تحقیقات فعال زیادی در زمینه توسعه الگوریتم‌های دقیق برای مسائل NP-سخت با پیچیدگی بدترین حالت غیر بدیهی انجام شده‌اند (برای بررسی روش‌های مورد استفاده و نتایج به دست آمده، مقاله معنایی [۱۰] را ببینید). در میان مسائل مطالعه شده در این زمینه، «مجموعه مستقل ماکسیمم» (و نسخه‌های خاص آن)، یکی از مسائلی است که توجه ویژه‌ای را دریافت کرده است و محققان مختلف را به حرکت درآورده است.
در اینجا در بخش ۲، روشی کلی را ارائه می‌دهیم که بهبودهای پیچیدگی بدترین حالت از نمونه‌های «پراکنده» را در نمونه‌های «متراکم‌تر» منتشر می‌کند، که در اینجا چگالی (یا تراکم) یک نمونه برای مساله مورد بررسی مناسب است و به مقدار متوسط پارامتر نمونه آن اشاره دارد. ما این روش را «روش پایین به بالا» می‌نامیم. ایده اصلی دارای دو مولفه است: ۱) انتخاب معیار بازگشتی نمونه، و ۲) روشی برای حصول اطمینان از این که در نمونه‌های «متراکم‌تر»، انشعاب مناسبی (نسبت به معیار منتخب) رخ می‌دهد.
Abstract
We first propose a new method, called “bottom-up method”, that, informally, “propagates” improvement of the worst-case complexity for “sparse” instances to “denser” ones and we show an easy though non-trivial application of it to the MIN SET COVER problem. We then tackle MAX INDEPENDENT SET. Following the bottom-up method we propagate improvements of worst-case complexity from graphs of average degree d to graphs of average degree greater than d. Indeed, using algorithms for MAX INDEPENDENT SET in graphs of average degree 3, we tackle MAX INDEPENDENT SET in graphs of average degree 4, 5 and 6. Then, we combine the bottom-up technique with measure and conquer techniques to get improved running times for graphs of maximum degree 4, 5 and 6 but also for general graphs. The best computation bounds obtained for MAX INDEPENDENT SET are O *(1.1571n), O *(1.1918n) and O *(1.2071n), for graphs of maximum (or more generally average) degree 4, 5 and 6 respectively, and O *(1.2127n) for general graphs. These results improve upon the best known polynomial space results for these cases.
1 Introduction
Very active research has been recently conducted around the development of exact algorithms for NP-hard problems with non-trivial worst-case complexity (see the seminal paper [10] for a survey on both methods used and results obtained). Among the problems studied in this field, max independent set (and particular versions of it) is one of those that have received a very particular attention and mobilized numerous researchers.
Here, we propose in Section 2 a generic method that propagates improvements of worst-case complexity from “sparse” instances to “denser” (less sparse) ones, where the density of an instance is proper to the problem handled and refers to the average value of some parameter of its instance. We call this method “bottom-up method”. The basic idea here has two ingredients: (i) the choice of the recursive measure of the instance and (ii) a way to ensure that on “denser” instances, a good branching (wrt. the chosen measure) occurs.
(جهت بزرگ نمایی روی عکس کلیک نمایید)
چکیده
1. مقدمه
2. روش پایین به بالا
2.1. اهمیت معیار پیچیدگی بازگشتی: مورد پوشش مجموعه مینیمم
2.2. ایجاد انشعابی خوب: مورد مجموعه مستقل ماکسیمم
3. اصلاح تجزیه و تحلیل موردی برای گراف‌های با درجه متوسط ۴
4. هنگامی که روش پایین به بالا، معیار و تسخیر را براورده می‌سازد: بهبودهای نهایی و یک الگوریتم در گراف‌های کلی
5. نتیجه‌گیری
منابع
Abstract
1 Introduction
2 The Bottom-Up Method
2.1 The Importance of Recursive Complexity Measure: The Case of min set cover
2.2 Making a Good Branching: The Case of max independent set
3 Refined Case Analysis for Graphs of Average Degree 4
4 When Bottom-Up Meets Measure and Conquer: Final Improvements and an Algorithm in General Graphs
5 Conclusion
References
- ترجمه فارسی مقاله با فرمت ورد (word) با قابلیت ویرایش، بدون آرم سایت ای ترجمه
- ترجمه فارسی مقاله با فرمت pdf، بدون آرم سایت ای ترجمه