ملخص
In the distributed backup-placement problem [9] each node of a network has to select one neighbor, such that the maximum number of nodes that make the same selection is minimized. This is a natural relaxation of the perfect matching problem, in which each node is selected just by one neighbor. Previous (approximate) solutions for backup placement are non-trivial, even for simple graph topologies, such as dense graphs [5]. In this paper we devise an algorithm for dense graph topologies, including unit disk graphs, unit ball graphs, line graphs, graphs with bounded diversity, and many more. Our algorithm requires just one round, and is as simple as the following operation. Consider a circular list of neighborhood IDs, sorted in an ascending order, and select the ID that is next to the selecting vertex ID. Surprisingly, such a simple one-round strategy turns out to be very efficient for backup placement computation in dense networks. Not only that it improves the number of rounds of the solution, but also the approximation ratio is improved by a multiplicative factor of at least 2. Our new algorithm has several interesting implications. In particular, it gives rise to a (2 + ε)-approximation to maximum matching within O(log∗ n) rounds in dense networks. The resulting algorithm is very simple as well, in sharp contrast to previous algorithms that compute such a solution within this running time. Moreover, these algorithms are applicable to a narrower graph family than our algorithm. For the same graph family, the best previously-known result has O(log ∆ + log∗ n) running time [4]. Another interesting implication is the possibility to execute our backup placement algorithm as-is in the self-stabilizing setting. This makes it possible to simplify and improve other algorithms for the self-stabilizing setting, by employing helpful properties of backup placement.
اللغة الأصلية | الإنجليزيّة |
---|---|
عنوان منشور المضيف | 3rd SIAM Symposium on Simplicity in Algorithms, SOSA 2020 |
المحررون | Martin Farach-Colton, Inge Li Gortz |
ناشر | Society for Industrial and Applied Mathematics Publications |
الصفحات | 99-105 |
عدد الصفحات | 7 |
رقم المعيار الدولي للكتب (الإلكتروني) | 9781713807377 |
حالة النشر | نُشِر - 2020 |
الحدث | 3rd SIAM Symposium on Simplicity in Algorithms, SOSA 2020 - Salt Lake City, الولايات المتّحدة المدة: ٦ يناير ٢٠٢٠ → ٧ يناير ٢٠٢٠ |
سلسلة المنشورات
الاسم | 3rd SIAM Symposium on Simplicity in Algorithms, SOSA 2020 |
---|
!!Conference
!!Conference | 3rd SIAM Symposium on Simplicity in Algorithms, SOSA 2020 |
---|---|
الدولة/الإقليم | الولايات المتّحدة |
المدينة | Salt Lake City |
المدة | ٦/٠١/٢٠ → ٧/٠١/٢٠ |
ملاحظة ببليوغرافية
Publisher Copyright:© 2020 by SIAM.