Approximation Algorithms and Semidefinite Programming

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

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

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

Semidefinite programs constitute one of the largest classes of optimization problems that can be solved with reasonable efficiency - both in theory and practice. They play a key role in a variety of research areas, such as combinatorial optimization, approximation algorithms, computational complexity, graph theory, geometry, real algebraic geometry and quantum computing. This book is an introduction to selected aspects of semidefinite programming and its use in approximation algorithms. It covers the basics but also a significant amount of recent and more advanced material.

There are many computational problems, such as MAXCUT, for which one cannot reasonably expect to obtain an exact solution efficiently, and in such case, one has to settle for approximate solutions. For MAXCUT and its relatives, exciting recent results suggest that semidefinite programming is probably the ultimate tool. Indeed, assuming the Unique Games Conjecture, a plausible but as yet unproven hypothesis, it was shown that for these problems, known algorithms based on semidefinite programming deliver the best possible approximation ratios among all polynomial-time algorithms.

This book follows the “semidefinite side” of these developments, presenting some of the main ideas behind approximation algorithms based on semidefinite programming. It develops the basic theory of semidefinite programming, presents one of the known efficient algorithms in detail, and describes the principles of some others. It also includes applications, focusing on approximation algorithms.