Hamiltonian cycle problem and Markov chains

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

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

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

This research monograph summarizes a line of research that maps certain classical problems of discrete mathematics and operations research - such as the Hamiltonian Cycle and the Travelling Salesman Problems - into convex domains where continuum analysis can be carried out. Arguably, the inherent difficulty of these, now classical, problems stems precisely from the discrete nature of domains in which these problems are posed. The convexification of domains underpinning these results is achieved by assigning probabilistic interpretation to key elements of the original deterministic problems. In particular, the approaches summarized here build on a technique that embeds Hamiltonian Cycle and Travelling Salesman Problems in a structured singularly perturbed Markov decision process. The unifying idea is to interpret subgraphs traced out by deterministic policies (including Hamiltonian cycles, if any) as extreme points of a convex polyhedron in a space filled with randomized policies.

The above innovative approach has now evolved to the point where there are many, both theoretical and algorithmic, results that exploit the nexus between graph theoretic structures and both probabilistic and algebraic entities of related Markov chains. The latter include moments of first return times, limiting frequencies of visits to nodes, or the spectra of certain matrices traditionally associated with the analysis of Markov chains. However, these results and algorithms are dispersed over many research papers appearing in journals catering to disparate audiences. As a result, the published manuscripts are often written in a very terse manner and use disparate notation, thereby making it difficult for new researchers to make use of the many reported advances.

Hence the main purpose of this book is to present a concise and yet easily accessible synthesis of the majority of the theoretical and algorithmic results obtained so far. In addition, the book discusses numerous open questions and problems that arise from this body of work and which are yet to be fully solved. The approach casts the Hamiltonian Cycle Problem in a mathematical framework that permits analytical concepts and techniques, not used hitherto in this context, to be brought to bear to further clarify both the underlying difficulty of NP-completeness of this problem and the relative exceptionality of truly difficult instances. Finally, the material is arranged in such a manner that the introductory chapters require very little mathematical background and discuss instances of graphs with interesting structures that motivated a lot of the research in this topic. More difficult results are introduced later and are illustrated with numerous examples.