[{"status":"public","_id":"11866","page":"489 - 498","publisher":"Association for Computing Machinery","conference":{"start_date":"2016-06-19","end_date":"2016-06-21","name":"STOC: Symposium on Theory of Computing","location":"Cambridge, MA, United States"},"scopus_import":"1","title":"A deterministic almost-tight distributed algorithm for approximating single-source shortest paths","main_file_link":[{"url":"https://arxiv.org/abs/1504.07056","open_access":"1"}],"type":"conference","publication_identifier":{"isbn":["978-145034132-5"],"issn":["0737-8017"]},"publication_status":"published","date_updated":"2024-11-06T12:19:26Z","extern":"1","abstract":[{"text":"We present a deterministic (1+o(1))-approximation O(n1/2+o(1)+D1+o(1))-time algorithm for solving the single-source shortest paths problem on distributed weighted networks (the CONGEST model); here n is the number of nodes in the network and D is its (hop) diameter. This is the first non-trivial deterministic algorithm for this problem. It also improves (i) the running time of the randomized (1+o(1))-approximation Õ(n1/2D1/4+D)-time algorithm of Nanongkai [STOC 2014] by a factor of as large as n1/8, and (ii) the O(є−1logє−1)-approximation factor of Lenzen and Patt-Shamir’s Õ(n1/2+є+D)-time algorithm [STOC 2013] within the same running time. Our running time matches the known time lower bound of Ω(n1/2/logn + D) [Das Sarma et al. STOC 2011] modulo some lower-order terms, thus essentially settling the status of this problem which was raised at least a decade ago [Elkin SIGACT News 2004]. It also implies a (2+o(1))-approximation O(n1/2+o(1)+D1+o(1))-time algorithm for approximating a network’s weighted diameter which almost matches the lower bound by Holzer et al. [PODC 2012].\r\n\r\nIn achieving this result, we develop two techniques which might be of independent interest and useful in other settings: (i) a deterministic process that replaces the “hitting set argument” commonly used for shortest paths computation in various settings, and (ii) a simple, deterministic, construction of an (no(1), o(1))-hop set of size O(n1+o(1)). We combine these techniques with many distributed algorithmic techniques, some of which from problems that are not directly related to shortest paths, e.g. ruling sets [Goldberg et al. STOC 1987], source detection [Lenzen, Peleg PODC 2013], and partial distance estimation [Lenzen, Patt-Shamir PODC 2015]. Our hop set construction also leads to single-source shortest paths algorithms in two other settings: (i) a (1+o(1))-approximation O(no(1))-time algorithm on congested cliques, and (ii) a (1+o(1))-approximation O(no(1)logW)-pass O(n1+o(1)logW)-space streaming algorithm, when edge weights are in {1, 2, …, W}. The first result answers an open problem in [Nanongkai, STOC 2014]. The second result partially answers an open problem raised by McGregor in 2006 [<pre>sublinear.info</pre>, Problem 14].","lang":"eng"}],"doi":"10.1145/2897518.2897638","article_processing_charge":"No","day":"01","author":[{"first_name":"Monika H","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"last_name":"Krinninger","full_name":"Krinninger, Sebastian","first_name":"Sebastian"},{"full_name":"Nanongkai, Danupon","first_name":"Danupon","last_name":"Nanongkai"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","month":"06","oa":1,"oa_version":"Preprint","external_id":{"arxiv":["1504.07056"]},"arxiv":1,"date_published":"2016-06-01T00:00:00Z","citation":{"ieee":"M. Henzinger, S. Krinninger, and D. Nanongkai, “A deterministic almost-tight distributed algorithm for approximating single-source shortest paths,” in <i>48th Annual ACM SIGACT Symposium on Theory of Computing</i>, Cambridge, MA, United States, 2016, pp. 489–498.","ista":"Henzinger M, Krinninger S, Nanongkai D. 2016. A deterministic almost-tight distributed algorithm for approximating single-source shortest paths. 48th Annual ACM SIGACT Symposium on Theory of Computing. STOC: Symposium on Theory of Computing, 489–498.","ama":"Henzinger M, Krinninger S, Nanongkai D. A deterministic almost-tight distributed algorithm for approximating single-source shortest paths. In: <i>48th Annual ACM SIGACT Symposium on Theory of Computing</i>. Association for Computing Machinery; 2016:489-498. doi:<a href=\"https://doi.org/10.1145/2897518.2897638\">10.1145/2897518.2897638</a>","apa":"Henzinger, M., Krinninger, S., &#38; Nanongkai, D. (2016). A deterministic almost-tight distributed algorithm for approximating single-source shortest paths. In <i>48th Annual ACM SIGACT Symposium on Theory of Computing</i> (pp. 489–498). Cambridge, MA, United States: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/2897518.2897638\">https://doi.org/10.1145/2897518.2897638</a>","mla":"Henzinger, Monika, et al. “A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths.” <i>48th Annual ACM SIGACT Symposium on Theory of Computing</i>, Association for Computing Machinery, 2016, pp. 489–98, doi:<a href=\"https://doi.org/10.1145/2897518.2897638\">10.1145/2897518.2897638</a>.","short":"M. Henzinger, S. Krinninger, D. Nanongkai, in:, 48th Annual ACM SIGACT Symposium on Theory of Computing, Association for Computing Machinery, 2016, pp. 489–498.","chicago":"Henzinger, Monika, Sebastian Krinninger, and Danupon Nanongkai. “A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths.” In <i>48th Annual ACM SIGACT Symposium on Theory of Computing</i>, 489–98. Association for Computing Machinery, 2016. <a href=\"https://doi.org/10.1145/2897518.2897638\">https://doi.org/10.1145/2897518.2897638</a>."},"date_created":"2022-08-16T09:19:31Z","year":"2016","publication":"48th Annual ACM SIGACT Symposium on Theory of Computing","language":[{"iso":"eng"}],"quality_controlled":"1"},{"publication_identifier":{"issn":["0737-8017"],"isbn":["978-145034132-5"]},"type":"conference","date_updated":"2024-11-06T12:19:37Z","publication_status":"published","doi":"10.1145/2897518.2897568","extern":"1","abstract":[{"lang":"eng","text":"We present two deterministic dynamic algorithms for the maximum matching problem. (1) An algorithm that maintains a (2+є)-approximate maximum matching in general graphs with O(poly(logn, 1/є)) update time. (2) An algorithm that maintains an αK approximation of the value of the maximum matching with O(n2/K) update time in bipartite graphs, for every sufficiently large constant positive integer K. Here, 1≤ αK < 2 is a constant determined by the value of K. Result (1) is the first deterministic algorithm that can maintain an o(logn)-approximate maximum matching with polylogarithmic update time, improving the seminal result of Onak et al. [STOC 2010]. Its approximation guarantee almost matches the guarantee of the best randomized polylogarithmic update time algorithm [Baswana et al. FOCS 2011]. Result (2) achieves a better-than-two approximation with arbitrarily small polynomial update time on bipartite graphs. Previously the best update time for this problem was O(m1/4) [Bernstein et al. ICALP 2015], where m is the current number of edges in the graph."}],"status":"public","title":"New deterministic approximation algorithms for fully dynamic matching","scopus_import":"1","_id":"11867","page":"398 - 411","conference":{"location":"Cambridge, MA, United States","name":"STOC: Symposium on Theory of Computing","end_date":"2016-06-21","start_date":"2016-06-19"},"publisher":"Association for Computing Machinery","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1604.05765"}],"arxiv":1,"external_id":{"arxiv":["1604.05765"]},"date_published":"2016-06-01T00:00:00Z","citation":{"ama":"Bhattacharya S, Henzinger M, Nanongkai D. New deterministic approximation algorithms for fully dynamic matching. In: <i>48th Annual ACM SIGACT Symposium on Theory of Computing</i>. Association for Computing Machinery; 2016:398-411. doi:<a href=\"https://doi.org/10.1145/2897518.2897568\">10.1145/2897518.2897568</a>","ista":"Bhattacharya S, Henzinger M, Nanongkai D. 2016. New deterministic approximation algorithms for fully dynamic matching. 48th Annual ACM SIGACT Symposium on Theory of Computing. STOC: Symposium on Theory of Computing, 398–411.","ieee":"S. Bhattacharya, M. Henzinger, and D. Nanongkai, “New deterministic approximation algorithms for fully dynamic matching,” in <i>48th Annual ACM SIGACT Symposium on Theory of Computing</i>, Cambridge, MA, United States, 2016, pp. 398–411.","chicago":"Bhattacharya, Sayan, Monika Henzinger, and Danupon Nanongkai. “New Deterministic Approximation Algorithms for Fully Dynamic Matching.” In <i>48th Annual ACM SIGACT Symposium on Theory of Computing</i>, 398–411. Association for Computing Machinery, 2016. <a href=\"https://doi.org/10.1145/2897518.2897568\">https://doi.org/10.1145/2897518.2897568</a>.","short":"S. Bhattacharya, M. Henzinger, D. Nanongkai, in:, 48th Annual ACM SIGACT Symposium on Theory of Computing, Association for Computing Machinery, 2016, pp. 398–411.","mla":"Bhattacharya, Sayan, et al. “New Deterministic Approximation Algorithms for Fully Dynamic Matching.” <i>48th Annual ACM SIGACT Symposium on Theory of Computing</i>, Association for Computing Machinery, 2016, pp. 398–411, doi:<a href=\"https://doi.org/10.1145/2897518.2897568\">10.1145/2897518.2897568</a>.","apa":"Bhattacharya, S., Henzinger, M., &#38; Nanongkai, D. (2016). New deterministic approximation algorithms for fully dynamic matching. In <i>48th Annual ACM SIGACT Symposium on Theory of Computing</i> (pp. 398–411). Cambridge, MA, United States: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/2897518.2897568\">https://doi.org/10.1145/2897518.2897568</a>"},"date_created":"2022-08-16T09:27:35Z","publication":"48th Annual ACM SIGACT Symposium on Theory of Computing","year":"2016","language":[{"iso":"eng"}],"quality_controlled":"1","article_processing_charge":"No","day":"01","month":"06","author":[{"first_name":"Sayan","full_name":"Bhattacharya, Sayan","last_name":"Bhattacharya"},{"orcid":"0000-0002-5008-6530","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H","first_name":"Monika H"},{"full_name":"Nanongkai, Danupon","first_name":"Danupon","last_name":"Nanongkai"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa":1,"oa_version":"Preprint"}]