Probability Theory of Classical Euclidean Optimization Problems

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

This monograph describes the stochastic behavior of the solutions to the classic problems of Euclidean combinatorial optimization, computational geometry, and operations research. Using two-sided additivity and isoperimetry, it formulates general methods describing the total edge length of random graphs in Euclidean space. The approach furnishes strong laws of large numbers, large deviations, and rates of convergence for solutions to the random versions of various classic optimization problems, including the traveling salesman, minimal spanning tree, minimal matching, minimal triangulation, two-factor, and k-median problems. Essentially self-contained, this monograph may be read by probabilists, combinatorialists, graph theorists, and theoretical computer scientists.