Geometric Algorithms and Combinatorial Optimization

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

Since the publication of the first edition of our book, geometric algorithms and combinatorial optimization have kept growing at the same fast pace as before. Nevertheless, we do not feel that the ongoing research has made this book outdated. Rather, it seems that many of the new results build on the models, algorithms, and theorems presented here. For instance, the celebrated Dyer-Frieze-Kannan algorithm for approximating the volume of a convex body is based on the oracle model of convex bodies and uses the ellipsoid method as a preprocessing technique. The polynomial time equivalence of optimization, separation, and membership has become a commonly employed tool in the study of the complexity of combinatorial optimization problems and in the newly developing field of computational convexity. Implementations of the basis reduction algorithm can be found in various computer algebra software systems. On the other hand, several of the open problems discussed in the first edition are still unsolved. For example, there are still no combinatorial polynomial time algorithms known for minimizing a submodular function or finding a maximum clique in a perfect graph. Moreover, despite the success of the interior point methods for the solution of explicitly given linear programs there is still no method known that solves implicitly given linear programs, such as those described in this book, and that is both practically and theoretically efficient. In particular, it is not known how to adapt interior point methods to such linear programs.