عنوان پایان‌نامه
الگوریتم های تقریبی اولیه –دوگان برای مسائل طراحی شبکه
- رشته تحصیلی
- مهندسی کامپیوتر- آلگوریتم ها و محاسبات
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه پردیس یک فنی شماره ثبت: 73..;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 67515
- تاریخ دفاع
- ۱۲ شهریور ۱۳۹۳
- دانشجو
- بهناز بخشی زاده
- استاد راهنما
- دارا معظمی
- چکیده
- مسائل مرتبط با طراحی شبکه¬ها با گستردگی و پیچیدگی روز¬افزون خود دارای اهمیت ویژه¬ای هستند. این مسائل علاوه بر ارزش آکادمیک، دارای کاربردهای گوناگونی از جمله نگه¬داری توان الکتریکی در شبکه¬ها تا پایداری محاسباتی هستند. از سویی این مسائل از زمره مسائل NP-سخت می¬باشند که برای این گروه از مسائل تا وقتی¬که P?NP نمی¬توانیم الگوریتمی بیابیم که جواب بهینه را در زمان¬چندجمله¬ای به¬دست دهد و این موضوع اهمیت یافتن یک الگوریتم تقریبی مفید برای این مسائل را افزایش می¬دهد. در این پژوهش از میان مسائل مختلف طراحی شبکه، نمونه راس-وزن¬دار مسائل مجموعه رئوس بازخوردی، درخت اشتاینر و درخت اشتاینر جمع¬آوری امتیاز به¬عنوان بستر مطالعه انتخاب شده است و بهترین الگوریتم¬های موجود برای این مسائل مورد بررسی قرارگرفته است و از میان رویکرد¬های مختلف الگوریتم¬های تقریبی، از رویه اولیه-دوگان برای طراحی الگوریتمی کارا استفاده¬می¬کنیم. در سه سال اخیر توجه بسیار زیادی به مسائل اشتاینر شده است، به عنوان مثال، در گراف¬های هامنی برای مسئله¬ی درخت اشتاینر و مسئله¬ی جنگل اشتاینر جمع¬آوری امتیاز یک رویه تقریبی در زمان چندجمله¬ای ارائه شده¬است. با این وجود برای مسائل اشتاینر راس¬-وزن¬دار، با توجه به کاهش با حفظ تقریب ساده از پوشش مجموعه¬ای، مشخص می¬شود که مسئله جنگل اشتاینر ¬راس-وزن¬دار درحالت کلی نمی¬تواند با فاکتور تقریب بهتر از (1-O(1) ) ln?k تقریب زده شود. ماس و ربانی الگوریتم O(log n)-تقریبی برای مسئله¬ی جنگل اشتاینر جمع¬آوری امتیاز ارائه داده¬اند که تا کنون بهترین فاکتور تقریبی است که برای این مسئله ارائه¬شده است. در این پژوهش الگوریتم تقریبی جدیدی معرفی می¬کنیم که دارای همان فاکتور تقریب است ولی در برخی شرایط پاسخ¬های بهینه¬تری نسبت به الگوریتم نام¬برده به¬دست می¬دهد و در پایان فاکتور تقریب این الگوریتم جدید را اثبات خواهیم کرد.
- Abstract
- In this thesis we study the node-weighted version of network design problems and the best presented primal-dual algorithms which give a 2.4 approximation for a class of node-weighted network design problems in planar graphs. This class includes node-weighted Steiner Forest problem and other node weighted problems in planar graphs that can be expressed using (0,1)-proper functions. Yannakakis has given an NP-hardness proof for many vertex deletion problems restricted to planar graphs which applies to all problems that we consider. Node-weighted Steiner problems have been studied theoretically in many different settings. Applications of such problems range from maintenance of electric power networks to computational sustainability. In contrast, for more general node-weighted versions constant factor approximations via primal-dual algorithms remain the state of the art, while no APX-hardness is known. We study the node-weighted version of the Prize Collecting Steiner Tree problem. Moss and Rabani claimed an O(log n)-approximation algorithm for the problem using a primal-dual approach. We propose a new algorithm which is more involved and introduces new ideas in primal dual approach for network design problems. For edge-weighted versions of these problems, as well as versions with uniform node weights, there has been significant progress in obtaining PTASs recently.
