Document Open Access Logo

Mending Partial Solutions with Few Changes

Authors Darya Melnyk, Jukka Suomela, Neven Villani

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2022.21.pdf
  • Filesize: 0.9 MB
  • 17 pages

Document Identifiers

Author Details

Darya Melnyk
  • Aalto University, Finland
Jukka Suomela
  • Aalto University, Finland
Neven Villani
  • Aalto University, Finland
  • École Normale Supérieure Paris-Saclay, Université Paris-Saclay, France

Funding

This work was supported in part by the Academy of Finland, Grant 333837.

Cite As Get BibTex

Darya Melnyk, Jukka Suomela, and Neven Villani. Mending Partial Solutions with Few Changes. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 21:1-21:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.OPODIS.2022.21

Abstract

In this paper, we study the notion of mending: given a partial solution to a graph problem, how much effort is needed to take one step towards a proper solution? For example, if we have a partial coloring of a graph, how hard is it to properly color one more node?
In prior work (SIROCCO 2022), this question was formalized and studied from the perspective of mending radius: if there is a hole that we need to patch, how far do we need to modify the solution? In this work, we investigate a complementary notion of mending volume: how many nodes need to be modified to patch a hole?
We focus on the case of locally checkable labeling problems (LCLs) in trees, and show that already in this setting there are two infinite hierarchies of problems: for infinitely many values 0 < α ≤ 1, there is an LCL problem with mending volume Θ(n^α), and for infinitely many values k ≥ 1, there is an LCL problem with mending volume Θ(log^k n). Hence the mendability of LCL problems on trees is a much more fine-grained question than what one would expect based on the mending radius alone.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed computing models
  • Theory of computation → Parallel computing models
Keywords
  • mending
  • LCL problems
  • volume model

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Emile Aarts and Jan Karel Lenstra, editors. Local Search in Combinatorial Optimization. Princeton University Press, 2003. URL: https://doi.org/10.2307/j.ctv346t9c.
  2. Yehuda Afek, Shay Kutten, and Moti Yung. Memory-efficient self stabilizing protocols for general networks. In Jan van Leeuwen and Nicola Santoro, editors, Distributed Algorithms, pages 15-28, Berlin, Heidelberg, 1991. Springer Berlin Heidelberg. Google Scholar
  3. Eric Angel. A Survey of Approximation Results for Local Search Algorithms, pages 30-73. Springer Berlin Heidelberg, Berlin, Heidelberg, 2006. URL: https://doi.org/10.1007/11671541_2.
  4. Esther M. Arkin and Refael Hassin. On Local Search for Weighted k-Set Packing. Mathematics of Operations Research, 23(3):640-648, 1998. URL: https://doi.org/10.1287/moor.23.3.640.
  5. Giorgio Ausiello and Marco Protasi. Local search, reducibility and approximability of NP-optimization problems. Information Processing Letters, 54(2):73-79, 1995. URL: https://doi.org/10.1016/0020-0190(95)00006-X.
  6. Baruch Awerbuch, Boaz Patt-Shamir, and George Varghese. Self-stabilization by local checking and correction (extended abstract). In Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, SFCS '91, pages 268-277, USA, 1991. IEEE Computer Society. URL: https://doi.org/10.1109/SFCS.1991.185378.
  7. Baruch Awerbuch, Boaz Patt-Shamir, George Varghese, and Shlomi Dolev. Self-stabilization by local checking and global reset. In Gerard Tel and Paul Vitányi, editors, Distributed Algorithms, pages 326-339, Berlin, Heidelberg, 1994. Springer Berlin Heidelberg. Google Scholar
  8. Vineet Bafna, Babu Narayanan, and R. Ravi. Nonoverlapping local alignments (weighted independent sets of axis-parallel rectangles). Discrete Applied Mathematics, 71(1):41-53, 1996. URL: https://doi.org/10.1016/S0166-218X(96)00063-7.
  9. Alkida Balliu, Juho Hirvonen, Darya Melnyk, Dennis Olivetti, Joel Rybicki, and Jukka Suomela. Local Mending. In Structural Information and Communication Complexity, 2022. URL: https://doi.org/10.1007/978-3-031-09993-9_1.
  10. Joffroy Beauquier, Sylvie Delaët, Shlomi Dolev, and Sébastien Tixeuil. Transient fault detectors. Distrib. Comput., 20(1):39-51, July 2007. URL: https://doi.org/10.1007/s00446-007-0029-x.
  11. Sebastian Brandt, Christoph Grunau, and Václav Rozhoň. The Randomized Local Computation Complexity of the Lovász Local Lemma. In Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing, PODC'21, 2021. URL: https://doi.org/10.1145/3465084.3467931.
  12. M. Chams, A. Hertz, and D. de Werra. Some experiments with simulated annealing for coloring graphs. European Journal of Operational Research, 32(2):260-266, 1987. Third EURO Summer Institute Special Issue Decision Making in an Uncertain World. URL: https://doi.org/10.1016/S0377-2217(87)80148-0.
  13. Barun Chandra and Magnús M Halldórsson. Greedy Local Improvement and Weighted Set Packing Approximation. Journal of Algorithms, 39(2):223-240, 2001. URL: https://doi.org/10.1006/jagm.2000.1155.
  14. Shiri Chechik and Doron Mukhtar. Optimal Distributed Coloring Algorithms for Planar Graphs in the LOCAL Model. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019. Google Scholar
  15. Johanne Cohen, Laurence Pilard, Mikaël Rabie, and Jonas Sénizergues. Making Self-Stabilizing any Locally Greedy Problem, 2022. URL: https://doi.org/10.48550/arXiv.2208.14700.
  16. Philippe Galinier and Alain Hertz. A survey of local search methods for graph coloring. Computers & Operations Research, 33(9):2547-2562, 2006. Part Special Issue: Anniversary Focused Issue of Computers & Operations Research on Tabu Search. URL: https://doi.org/10.1016/j.cor.2005.07.028.
  17. Magnús M. Halldórsson. Approximating Discrete Collections via Local Improvements. In Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '95, pages 160-169, 1995. URL: https://doi.org/10.5555/313651.313687.
  18. David G. Harris, Hsin-Hao Su, and Hoa T. Vu. On the Locality of Nash-Williams Forest Decomposition and Star-Forest Decomposition. In Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing, PODC'21, 2021. URL: https://doi.org/10.1145/3465084.3467908.
  19. David S. Johnson, Christos H. Papadimitriou, and Mihalis Yannakakis. How easy is local search? Journal of Computer and System Sciences, 37(1):79-100, 1988. URL: https://doi.org/10.1016/0022-0000(88)90046-3.
  20. Michael König and Roger Wattenhofer. On Local Fixing. In Principles of Distributed Systems, 2013. URL: https://doi.org/10.1007/978-3-319-03850-6_14.
  21. S. Kutten and D. Peleg. Tight fault locality. In Proceedings of IEEE 36th Annual Foundations of Computer Science, 1995. URL: https://doi.org/10.1109/SFCS.1995.492672.
  22. Moni Naor and Larry Stockmeyer. What Can be Computed Locally? SIAM Journal on Computing, 24(6):1259-1277, 1995. URL: https://doi.org/10.1137/S0097539793254571.
  23. Alessandro Panconesi and Aravind Srinivasan. The local nature of Δ-coloring and its algorithmic applications. Combinatorica, 15(2):255-280, 1995. URL: https://doi.org/10.1007/BF01200759.
  24. Silvia Richter, Malte Helmert, and Charles Gretton. A Stochastic Local Search Approach to Vertex Cover. In KI 2007: Advances in Artificial Intelligence, pages 412-426, 2007. URL: https://doi.org/10.1007/978-3-540-74565-5_31.
  25. Will Rosenbaum and Jukka Suomela. Seeing Far vs. Seeing Wide: Volume Complexity of Local Graph Problems. In Proceedings of the 39th Symposium on Principles of Distributed Computing, PODC '20, 2020. URL: https://doi.org/10.1145/3382734.3405721.
  26. Yukiko Yamauchi and Sébastien Tixeuil. Monotonic stabilization. In Chenyang Lu, Toshimitsu Masuzawa, and Mohamed Mosbah, editors, Principles of Distributed Systems, pages 475-490, Berlin, Heidelberg, 2010. Springer Berlin Heidelberg. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact