Distributed Backup Placement in One Round and its Applications to Maximum Matching Approximation and Self-Stabilization

نتاج البحث: فصل من :كتاب / تقرير / مؤتمرمنشور من مؤتمرمراجعة النظراء

ملخص

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

!!Conference3rd SIAM Symposium on Simplicity in Algorithms, SOSA 2020
الدولة/الإقليمالولايات المتّحدة
المدينةSalt Lake City
المدة٦/٠١/٢٠٧/٠١/٢٠

ملاحظة ببليوغرافية

Publisher Copyright:
© 2020 by SIAM.

بصمة

أدرس بدقة موضوعات البحث “Distributed Backup Placement in One Round and its Applications to Maximum Matching Approximation and Self-Stabilization'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا