عنوان پایان‌نامه
بررسی وبکار گیری زیر پیمانگی در مسائل بهینه سازی
- رشته تحصیلی
- مهندسی کامپیوتر- آلگوریتم ها و محاسبات
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه پردیس یک فنی شماره ثبت: 12..;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 46155
- تاریخ دفاع
- ۱۵ شهریور ۱۳۸۹
- دانشجو
- سلمان فدائی
- استاد راهنما
- علی معینی
- چکیده
- بیشینه‌سازی مسائل زیرپیمانه‌ای در علوم کامپیوتر نظری و سایر علوم وابسته اهمیت بسزائی دارد. این قبیل مسائل از نظر سختی در دسته مسائل-NP سخت قرار می‌گیرند. لذا یافتن الگوریتمهای تقریبی مناسب که هم از نظر زمان اجرا و هم از نظر ضریب دقت قابل قبول باشند، بسیار مورد نیاز است. ما در این پایان‌نامه در ابتدا یک مرور کلی بر روشهای مورد استفاده برای حل این مسائل داشته سپس با اعمال روشهای نوآورانه، بعضی مسائل مهم بیشینه‌سازی را از نظر ضریب دقت و یا سرعت و سادگی الگوریتم بهبود داده‌ایم. مسائلی که مورد بررسی قرار گرفتند و نتایج مهم حاصله از اعمال روشهای جدید روی هرکدام به شرح زیر است: • بیشینه‌سازی توابع زیرپیمانه‌ای غیریکنوا محدود به کاردینالیتی و کاردینالیتی دقیق: برای این مسائل الگوریتمهای ساده‌تر و سریعتر ارائه شد. • بیشینه‌سازی توابع زیرپیمانه‌ای غیریکنوا محدود به k کوله‌پشتی: در اینجا الگوریتم با ضریب تقریب بهتر ارائه شد. • بیشینه‌سازی توابع زیرپیمانه‌ای غیریکنوا محدود به پلی‌توپ بسته: این مسأله تاکنون مورد بررسی قرار نگرفته بود و اولین ضریب تقریب ثابت برای این مسأله ارائه شد.
- Abstract
- Recently, Submodularity has attained an important role in computer science fields. The problems of maximizing submodular set functions are NP-hard, and, consequently, to tackle these kinds of problems we need to find effective approximation algorithms. In this thesis, at first we had a survey on the methods used for the maximization problems and then by applying innovative methods, we achieved some faster algorithms or algorithms with better approximation ratios. Our most important results are as follows: • Maximizing non-monotone submodular functions subject to a cardinality or an exact cardinality constraint. In this case, we achieved simpler and faster algorithms. • Maximizing non-monotone submodular functions with respect to a cardinality constraint or constant number of cardinality constraints. Here, we achieved a better approximation factor. • Maximizing non-monotone submodular functions subject to any solvable packing polytope. This problem has not been considered before and we found the first constant approximation factor for the problem.
