Design and Analysis of Approximation Algorithms

این کتاب به عنوان یک کتاب درسی برای دانشجویان تحصیلات تکمیلی که در رشته علوم کامپیوتر نظری تحصیل می کنند در نظر گرفته شده است. همچنین می تواند به عنوان یک کتاب مرجع برای محققان در زمینه طراحی و تجزیه و تحلیل الگوریتم های تقریب استفاده شود. طراحی و تجزیه و تحلیل الگوریتم های تقریب یک دوره تحصیلات تکمیلی در علوم کامپیوتر نظری است که به طور گسترده در دانشگاه ها، هم در ایالات متحده و هم در خارج از کشور تدریس می شود. با این حال، کتاب های درسی بسیار کمی برای این دوره موجود است. در میان کتاب‌های موجود در بازار، اکثر کتاب‌ها از قالب مسئله‌محور پیروی می‌کنند. یعنی آنها بسیاری از مسائل مهم بهینه سازی ترکیبی و الگوریتم های تقریب آنها را جمع آوری کردند و آنها را بر اساس انواع یا کاربردهای مسائل، مانند مسائل هندسی، مسائل جبری و غیره سازماندهی کردند. چنین چینش مواد شاید راحت باشد. برای یک محقق که به دنبال مسائل و الگوریتم های مربوط به کار خود باشد، اما برای دانش آموز دشوار است که ایده های زیربنای الگوریتم های مختلف را دریافت کند. در کتاب جدیدی که در اینجا پیشنهاد شده است، ما از ارائه ساختارمندتر و تکنیک محور پیروی می کنیم. ما الگوریتم‌های تقریب را بر اساس تکنیک‌های طراحی الگوریتم‌ها در فصل‌های مختلف سازمان‌دهی می‌کنیم تا خواننده بتواند الگوریتم‌های تقریبی با ماهیت یکسان را با هم مطالعه کند. این به خواننده کمک می کند تا تکنیک های طراحی و تجزیه و تحلیل الگوریتم های تقریب را بهتر درک کند و همچنین به معلم کمک می کند تا ایده ها و تکنیک های الگوریتم های تقریب را به روشی یکپارچه تر ارائه دهد.

This book is intended to be used as a textbook for graduate students studying theoretical computer science. It can also be used as a reference book for researchers in the area of design and analysis of approximation algorithms. Design and Analysis of Approximation Algorithms is a graduate course in theoretical computer science taught widely in the universities, both in the United States and abroad. There are, however, very few textbooks available for this course. Among those available in the market, most books follow a problem-oriented format; that is, they collected many important combinatorial optimization problems and their approximation algorithms, and organized them based on the types, or applications, of problems, such as geometric-type problems, algebraic-type problems, etc. Such arrangement of materials is perhaps convenient for a researcher to look for the problems and algorithms related to his/her work, but is difficult for a student to capture the ideas underlying the various algorithms. In the new book proposed here, we follow a more structured, technique-oriented presentation. We organize approximation algorithms into different chapters, based on the design techniques for the algorithms, so that the reader can study approximation algorithms of the same nature together. It helps the reader to better understand the design and analysis techniques for approximation algorithms, and also helps the teacher to present the ideas and techniques of approximation algorithms in a more unified way.