Algorithmics for hard problems: introduction to combinatorial optimization, randomization, approximation, and heuristics

رویکردهای مختلفی برای حمله به مشکلات سخت وجود دارد. همه شایستگی‌ها، اما محدودیت‌های خود را دارند و به مجموعه‌ای از نظریه‌ها به عنوان پایه‌ای نیاز دارند. تعدادی کتاب برای هر یک وجود دارد: کتاب‌هایی در مورد نظریه پیچیدگی، کتاب‌های دیگر در مورد الگوریتم‌های تقریب، رویکردهای اکتشافی، پیچیدگی پارامتری، و با این حال کتاب‌هایی در مورد الگوریتم‌های تصادفی. این کتاب به طور کامل همه رویکردهای فوق را مورد بحث قرار می دهد. و شگفت انگیز است که در عین حال، این کار را به شیوه ای انجام می دهد که کتاب را نه تنها برای نظریه پردازان، بلکه برای افراد غیرمتخصص، برای دانش آموز یا معلم و برنامه نویس نیز در دسترس قرار می دهد. آیا شما فکر می کنید که دقت ریاضی و دسترسی با هم تناقض دارند؟ به این کتاب نگاه کنید تا دریابید که آنها به دلیل استعداد تحسین برانگیز نویسنده در ارائه مطالب خود به شیوه ای واضح و مختصر، با ایده ای که در پس این رویکرد به طور صریح و اغلب با مثالی آشکار بیان شده است، ندارند.
خواندن این کتاب تجربه زیبایی است و من می توانم آن را به همه علاقه مندان به یادگیری نحوه حل مسائل سخت توصیه کنم. این فقط یک ترکیب فشرده از مطالب کتاب های دیگر نیست. از آنجایی که رویکردهای مختلف را عمیقاً مورد بحث قرار می دهد، این شانس را دارد که آنها را با جزئیات مقایسه کند، و مهمتر از همه، برجسته کند که در چه شرایطی کدام رویکرد ممکن است ارزش کاوش را داشته باشد. هیچ کتابی در مورد یک نوع راه حل نمی تواند این کار را انجام دهد، اما این کتاب این کار را به روشی کاملاً جذاب انجام می دهد که می تواند به عنوان الگویی برای کتاب های درسی تئوری با سطح کلی بالا عمل کند. (پیتر ویدمایر)
ویرایش دوم بخشی را در مورد روش آرام سازی به برنامه ریزی خطی با تاکید بر گرد کردن، دوگانگی LP و طرحواره اولیه-دوگانه گسترش می دهد و ارائه ای مستقل و شفاف از طراحی ارائه می کند. الگوریتم‌های تصادفی‌سازی‌شده برای آزمایش اولیه.

There are several approaches to attack hard problems. All have their merits, but also their limitations, and need a large body of theory as their basis. A number of books for each one exist: books on complexity theory, others on approximation algorithms, heuristic approaches, parametrized complexity, and yet others on randomized algorithms. This book discusses thoroughly all of the above approaches. And, amazingly, at the same time, does this in a style that makes the book accessible not only to theoreticians, but also to the non-specialist, to the student or teacher, and to the programmer. Do you think that mathematical rigor and accessibility contradict? Look at this book to find out that they do not, due to the admirable talent of the author to present his material in a clear and concise way, with the idea behind the approach spelled out explicitly, often with a revealing example.
Reading this book is a beautiful experience and I can highly recommend it to anyone interested in learning how to solve hard problems. It is not just a condensed union of material from other books. Because it discusses the different approaches in depth, it has the chance to compare them in detail, and, most importantly, to highlight under what circumstances which approach might be worth exploring. No book on a single type of solution can do that, but this book does it in an absolutely fascinating way that can serve as a pattern for theory textbooks with a high level of generality. (Peter Widmayer)
The second edition extends the part on the method of relaxation to linear programming with an emphasis on rounding, LP-duality, and primal-dual schema, and provides a self-contained and transparent presentation of the design of randomized algorithms for primality testing.