--- _id: '11853' abstract: - lang: eng text: We present a deterministic dynamic algorithm for maintaining a (1+ε)f-approximate minimum cost set cover with O(f log(Cn)/ε^2) amortized update time, when the input set system is undergoing element insertions and deletions. Here, n denotes the number of elements, each element appears in at most f sets, and the cost of each set lies in the range [1/C, 1]. Our result, together with that of Gupta~et~al.~[STOC'17], implies that there is a deterministic algorithm for this problem with O(f log(Cn)) amortized update time and O(min(log n, f)) -approximation ratio, which nearly matches the polynomial-time hardness of approximation for minimum set cover in the static setting. Our update time is only O(log (Cn)) away from a trivial lower bound. Prior to our work, the previous best approximation ratio guaranteed by deterministic algorithms was O(f^2), which was due to Bhattacharya~et~al.~[ICALP`15]. In contrast, the only result that guaranteed O(f) -approximation was obtained very recently by Abboud~et~al.~[STOC`19], who designed a dynamic algorithm with (1+ε)f-approximation ratio and O(f^2 log n/ε) amortized update time. Besides the extra O(f) factor in the update time compared to our and Gupta~et~al.'s results, the Abboud~et~al.~algorithm is randomized, and works only when the adversary is oblivious and the sets are unweighted (each set has the same cost). We achieve our result via the primal-dual approach, by maintaining a fractional packing solution as a dual certificate. This approach was pursued previously by Bhattacharya~et~al.~and Gupta~et~al., but not in the recent paper by Abboud~et~al. Unlike previous primal-dual algorithms that try to satisfy some local constraints for individual sets at all time, our algorithm basically waits until the dual solution changes significantly globally, and fixes the solution only where the fix is needed. article_processing_charge: No author: - first_name: Sayan full_name: Bhattacharya, Sayan last_name: Bhattacharya - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 - first_name: Danupon full_name: Nanongkai, Danupon last_name: Nanongkai citation: ama: 'Bhattacharya S, Henzinger MH, Nanongkai D. A new deterministic algorithm for dynamic set cover. In: 60th Annual Symposium on Foundations of Computer Science. Institute of Electrical and Electronics Engineers; 2019:406-423. doi:10.1109/focs.2019.00033' apa: 'Bhattacharya, S., Henzinger, M. H., & Nanongkai, D. (2019). A new deterministic algorithm for dynamic set cover. In 60th Annual Symposium on Foundations of Computer Science (pp. 406–423). Baltimore, MD, United States: Institute of Electrical and Electronics Engineers. https://doi.org/10.1109/focs.2019.00033' chicago: Bhattacharya, Sayan, Monika H Henzinger, and Danupon Nanongkai. “A New Deterministic Algorithm for Dynamic Set Cover.” In 60th Annual Symposium on Foundations of Computer Science, 406–23. Institute of Electrical and Electronics Engineers, 2019. https://doi.org/10.1109/focs.2019.00033. ieee: S. Bhattacharya, M. H. Henzinger, and D. Nanongkai, “A new deterministic algorithm for dynamic set cover,” in 60th Annual Symposium on Foundations of Computer Science, Baltimore, MD, United States, 2019, pp. 406–423. ista: 'Bhattacharya S, Henzinger MH, Nanongkai D. 2019. A new deterministic algorithm for dynamic set cover. 60th Annual Symposium on Foundations of Computer Science. FOCS: Annual Symposium on Foundations of Computer Science, 406–423.' mla: Bhattacharya, Sayan, et al. “A New Deterministic Algorithm for Dynamic Set Cover.” 60th Annual Symposium on Foundations of Computer Science, Institute of Electrical and Electronics Engineers, 2019, pp. 406–23, doi:10.1109/focs.2019.00033. short: S. Bhattacharya, M.H. Henzinger, D. Nanongkai, in:, 60th Annual Symposium on Foundations of Computer Science, Institute of Electrical and Electronics Engineers, 2019, pp. 406–423. conference: end_date: 2019-11-12 location: Baltimore, MD, United States name: 'FOCS: Annual Symposium on Foundations of Computer Science' start_date: 2019-11-09 date_created: 2022-08-16T08:00:00Z date_published: 2019-11-01T00:00:00Z date_updated: 2023-02-17T09:50:37Z day: '01' doi: 10.1109/focs.2019.00033 extern: '1' external_id: arxiv: - '1909.11600' language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/1909.11600 month: '11' oa: 1 oa_version: Preprint page: 406-423 publication: 60th Annual Symposium on Foundations of Computer Science publication_identifier: eisbn: - 978-1-7281-4952-3 isbn: - 978-1-7281-4953-0 issn: - 2575-8454 publication_status: published publisher: Institute of Electrical and Electronics Engineers quality_controlled: '1' scopus_import: '1' status: public title: A new deterministic algorithm for dynamic set cover type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2019' ... --- _id: '11851' abstract: - lang: eng text: The minimum cut problem for an undirected edge-weighted graph asks us to divide its set of nodes into two blocks while minimizing the weighted sum of the cut edges. In this paper, we engineer the fastest known exact algorithm for the problem. State-of-the-art algorithms like the algorithm of Padberg and Rinaldi or the algorithm of Nagamochi, Ono and Ibaraki identify edges that can be contracted to reduce the graph size such that at least one minimum cut is maintained in the contracted graph. Our algorithm achieves improvements in running time over these algorithms by a multitude of techniques. First, we use a recently developed fast and parallel inexact minimum cut algorithm to obtain a better bound for the problem. Afterwards, we use reductions that depend on this bound to reduce the size of the graph much faster than previously possible. We use improved data structures to further lower the running time of our algorithm. Additionally, we parallelize the contraction routines of Nagamochi et al. . Overall, we arrive at a system that significantly outperforms the fastest state-of-the-art solvers for the exact minimum cut problem. article_number: '8820968' article_processing_charge: No author: - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 - first_name: Alexander full_name: Noe, Alexander last_name: Noe - first_name: Christian full_name: Schulz, Christian last_name: Schulz citation: ama: 'Henzinger MH, Noe A, Schulz C. Shared-memory exact minimum cuts. In: 33rd International Parallel and Distributed Processing Symposium. Institute of Electrical and Electronics Engineers; 2019. doi:10.1109/ipdps.2019.00013' apa: 'Henzinger, M. H., Noe, A., & Schulz, C. (2019). Shared-memory exact minimum cuts. In 33rd International Parallel and Distributed Processing Symposium. Rio de Janeiro, Brazil: Institute of Electrical and Electronics Engineers. https://doi.org/10.1109/ipdps.2019.00013' chicago: Henzinger, Monika H, Alexander Noe, and Christian Schulz. “Shared-Memory Exact Minimum Cuts.” In 33rd International Parallel and Distributed Processing Symposium. Institute of Electrical and Electronics Engineers, 2019. https://doi.org/10.1109/ipdps.2019.00013. ieee: M. H. Henzinger, A. Noe, and C. Schulz, “Shared-memory exact minimum cuts,” in 33rd International Parallel and Distributed Processing Symposium, Rio de Janeiro, Brazil, 2019. ista: 'Henzinger MH, Noe A, Schulz C. 2019. Shared-memory exact minimum cuts. 33rd International Parallel and Distributed Processing Symposium. IPDPS: International Parallel and Distributed Processing Symposium, 8820968.' mla: Henzinger, Monika H., et al. “Shared-Memory Exact Minimum Cuts.” 33rd International Parallel and Distributed Processing Symposium, 8820968, Institute of Electrical and Electronics Engineers, 2019, doi:10.1109/ipdps.2019.00013. short: M.H. Henzinger, A. Noe, C. Schulz, in:, 33rd International Parallel and Distributed Processing Symposium, Institute of Electrical and Electronics Engineers, 2019. conference: end_date: 2019-05-24 location: Rio de Janeiro, Brazil name: 'IPDPS: International Parallel and Distributed Processing Symposium' start_date: 2019-05-20 date_created: 2022-08-16T07:25:23Z date_published: 2019-05-01T00:00:00Z date_updated: 2023-02-21T16:30:34Z day: '01' doi: 10.1109/ipdps.2019.00013 extern: '1' external_id: arxiv: - '1808.05458' language: - iso: eng main_file_link: - url: https://arxiv.org/abs/1808.05458 month: '05' oa_version: Preprint publication: 33rd International Parallel and Distributed Processing Symposium publication_identifier: eisbn: - 978-1-7281-1246-6 eissn: - 1530-2075 isbn: - 978-1-7281-1247-3 publication_status: published publisher: Institute of Electrical and Electronics Engineers quality_controlled: '1' related_material: record: - id: '11851' relation: later_version status: public scopus_import: '1' status: public title: Shared-memory exact minimum cuts type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2019' ... --- _id: '11865' abstract: - lang: eng text: We present the first sublinear-time algorithm that can compute the edge connectivity λ of a network exactly on distributed message-passing networks (the CONGEST model), as long as the network contains no multi-edge. We present the first sublinear-time algorithm for a distributed message-passing network sto compute its edge connectivity λ exactly in the CONGEST model, as long as there are no parallel edges. Our algorithm takes Õ(n1−1/353D1/353+n1−1/706) time to compute λ and a cut of cardinality λ with high probability, where n and D are the number of nodes and the diameter of the network, respectively, and Õ hides polylogarithmic factors. This running time is sublinear in n (i.e. Õ(n1−є)) whenever D is. Previous sublinear-time distributed algorithms can solve this problem either (i) exactly only when λ=O(n1/8−є) [Thurimella PODC’95; Pritchard, Thurimella, ACM Trans. Algorithms’11; Nanongkai, Su, DISC’14] or (ii) approximately [Ghaffari, Kuhn, DISC’13; Nanongkai, Su, DISC’14]. To achieve this we develop and combine several new techniques. First, we design the first distributed algorithm that can compute a k-edge connectivity certificate for any k=O(n1−є) in time Õ(√nk+D). The previous sublinear-time algorithm can do so only when k=o(√n) [Thurimella PODC’95]. In fact, our algorithm can be turned into the first parallel algorithm with polylogarithmic depth and near-linear work. Previous near-linear work algorithms are essentially sequential and previous polylogarithmic-depth algorithms require Ω(mk) work in the worst case (e.g. [Karger, Motwani, STOC’93]). Second, we show that by combining the recent distributed expander decomposition technique of [Chang, Pettie, Zhang, SODA’19] with techniques from the sequential deterministic edge connectivity algorithm of [Kawarabayashi, Thorup, STOC’15], we can decompose the network into a sublinear number of clusters with small average diameter and without any mincut separating a cluster (except the “trivial” ones). This leads to a simplification of the Kawarabayashi-Thorup framework (except that we are randomized while they are deterministic). This might make this framework more useful in other models of computation. Finally, by extending the tree packing technique from [Karger STOC’96], we can find the minimum cut in time proportional to the number of components. As a byproduct of this technique, we obtain an Õ(n)-time algorithm for computing exact minimum cut for weighted graphs. article_processing_charge: No author: - first_name: Mohit full_name: Daga, Mohit last_name: Daga - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 - first_name: Danupon full_name: Nanongkai, Danupon last_name: Nanongkai - first_name: Thatchaphol full_name: Saranurak, Thatchaphol last_name: Saranurak citation: ama: 'Daga M, Henzinger MH, Nanongkai D, Saranurak T. Distributed edge connectivity in sublinear time. In: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. Association for Computing Machinery; 2019:343–354. doi:10.1145/3313276.3316346' apa: 'Daga, M., Henzinger, M. H., Nanongkai, D., & Saranurak, T. (2019). Distributed edge connectivity in sublinear time. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (pp. 343–354). Phoenix, AZ, United States: Association for Computing Machinery. https://doi.org/10.1145/3313276.3316346' chicago: Daga, Mohit, Monika H Henzinger, Danupon Nanongkai, and Thatchaphol Saranurak. “Distributed Edge Connectivity in Sublinear Time.” In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 343–354. Association for Computing Machinery, 2019. https://doi.org/10.1145/3313276.3316346. ieee: M. Daga, M. H. Henzinger, D. Nanongkai, and T. Saranurak, “Distributed edge connectivity in sublinear time,” in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, Phoenix, AZ, United States, 2019, pp. 343–354. ista: 'Daga M, Henzinger MH, Nanongkai D, Saranurak T. 2019. Distributed edge connectivity in sublinear time. Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. STOC: Symposium on Theory of Computing, 343–354.' mla: Daga, Mohit, et al. “Distributed Edge Connectivity in Sublinear Time.” Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, Association for Computing Machinery, 2019, pp. 343–354, doi:10.1145/3313276.3316346. short: M. Daga, M.H. Henzinger, D. Nanongkai, T. Saranurak, in:, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, Association for Computing Machinery, 2019, pp. 343–354. conference: end_date: 2019-06-26 location: Phoenix, AZ, United States name: 'STOC: Symposium on Theory of Computing' start_date: 2019-06-23 date_created: 2022-08-16T09:11:17Z date_published: 2019-06-01T00:00:00Z date_updated: 2023-02-17T10:26:25Z day: '01' doi: 10.1145/3313276.3316346 extern: '1' external_id: arxiv: - '1904.04341' language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/1904.04341 month: '06' oa: 1 oa_version: Preprint page: 343–354 publication: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing publication_identifier: isbn: - 978-1-4503-6705-9 issn: - 0737-8017 publication_status: published publisher: Association for Computing Machinery quality_controlled: '1' scopus_import: '1' status: public title: Distributed edge connectivity in sublinear time type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2019' ... --- _id: '11871' abstract: - lang: eng text: "Many dynamic graph algorithms have an amortized update time, rather than a stronger worst-case guarantee. But amortized data structures are not suitable for real-time systems, where each individual operation has to be executed quickly. For this reason, there exist many recent randomized results that aim to provide a guarantee stronger than amortized expected. The strongest possible guarantee for a randomized algorithm is that it is always correct (Las Vegas), and has high-probability worst-case update time, which gives a bound on the time for each individual operation that holds with high probability.\r\n\r\nIn this paper we present the first polylogarithmic high-probability worst-case time bounds for the dynamic spanner and the dynamic maximal matching problem.\r\n\r\n1.\t\r\nFor dynamic spanner, the only known o(n) worst-case bounds were O(n3/4) high-probability worst-case update time for maintaining a 3-spanner, and O(n5/9) for maintaining a 5-spanner. We give a O(1)k log3(n) high-probability worst-case time bound for maintaining a (2k – 1)-spanner, which yields the first worst-case polylog update time for all constant k. (All the results above maintain the optimal tradeoff of stretch 2k – 1 and Õ(n1+1/k) edges.)\r\n\r\n2.\t\r\nFor dynamic maximal matching, or dynamic 2-approximate maximum matching, no algorithm with o(n) worst-case time bound was known and we present an algorithm with O(log5 (n)) high-probability worst-case time; similar worst-case bounds existed only for maintaining a matching that was (2 + ∊)-approximate, and hence not maximal.\r\n\r\nOur results are achieved using a new approach for converting amortized guarantees to worst-case ones for randomized data structures by going through a third type of guarantee, which is a middle ground between the two above: an algorithm is said to have worst-case expected update time α if for every update σ, the expected time to process σ is at most α. Although stronger than amortized expected, the worst-case expected guarantee does not resolve the fundamental problem of amortization: a worst-case expected update time of O(1) still allows for the possibility that every 1/f(n) updates requires Θ(f(n)) time to process, for arbitrarily high f(n). In this paper we present a black-box reduction that converts any data structure with worst-case expected update time into one with a high-probability worst-case update time: the query time remains the same, while the update time increases by a factor of O(log2(n)).\r\n\r\nThus we achieve our results in two steps: (1) First we show how to convert existing dynamic graph algorithms with amortized expected polylogarithmic running times into algorithms with worst-case expected polylogarithmic running times. (2) Then we use our black-box reduction to achieve the polylogarithmic high-probability worst-case time bound. All our algorithms are Las-Vegas-type algorithms." article_processing_charge: No author: - first_name: Aaron full_name: Bernstein, Aaron last_name: Bernstein - first_name: Sebastian full_name: Forster, Sebastian last_name: Forster - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 citation: ama: 'Bernstein A, Forster S, Henzinger MH. A deamortization approach for dynamic spanner and dynamic maximal matching. In: 30th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics; 2019:1899-1918. doi:10.1137/1.9781611975482.115' apa: 'Bernstein, A., Forster, S., & Henzinger, M. H. (2019). A deamortization approach for dynamic spanner and dynamic maximal matching. In 30th Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 1899–1918). San Diego, CA, United States: Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611975482.115' chicago: Bernstein, Aaron, Sebastian Forster, and Monika H Henzinger. “A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching.” In 30th Annual ACM-SIAM Symposium on Discrete Algorithms, 1899–1918. Society for Industrial and Applied Mathematics, 2019. https://doi.org/10.1137/1.9781611975482.115. ieee: A. Bernstein, S. Forster, and M. H. Henzinger, “A deamortization approach for dynamic spanner and dynamic maximal matching,” in 30th Annual ACM-SIAM Symposium on Discrete Algorithms, San Diego, CA, United States, 2019, pp. 1899–1918. ista: 'Bernstein A, Forster S, Henzinger MH. 2019. A deamortization approach for dynamic spanner and dynamic maximal matching. 30th Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 1899–1918.' mla: Bernstein, Aaron, et al. “A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching.” 30th Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2019, pp. 1899–918, doi:10.1137/1.9781611975482.115. short: A. Bernstein, S. Forster, M.H. Henzinger, in:, 30th Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2019, pp. 1899–1918. conference: end_date: 2019-01-09 location: San Diego, CA, United States name: 'SODA: Symposium on Discrete Algorithms' start_date: 2019-01-06 date_created: 2022-08-16T09:50:33Z date_published: 2019-01-01T00:00:00Z date_updated: 2023-02-21T16:31:21Z day: '01' doi: 10.1137/1.9781611975482.115 extern: '1' external_id: arxiv: - '1810.10932' language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/1810.10932 month: '01' oa: 1 oa_version: Preprint page: 1899-1918 publication: 30th Annual ACM-SIAM Symposium on Discrete Algorithms publication_identifier: eisbn: - 978-1-61197-548-2 publication_status: published publisher: Society for Industrial and Applied Mathematics quality_controlled: '1' related_material: record: - id: '11871' relation: earlier_version status: public scopus_import: '1' status: public title: A deamortization approach for dynamic spanner and dynamic maximal matching type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2019' ... --- _id: '11898' abstract: - lang: eng text: "We build upon the recent papers by Weinstein and Yu (FOCS'16), Larsen (FOCS'12), and Clifford et al. (FOCS'15) to present a general framework that gives amortized lower bounds on the update and query times of dynamic data structures. Using our framework, we present two concrete results.\r\n(1) For the dynamic polynomial evaluation problem, where the polynomial is defined over a finite field of size n1+Ω(1) and has degree n, any dynamic data structure must either have an amortized update time of Ω((lgn/lglgn)2) or an amortized query time of Ω((lgn/lglgn)2).\r\n(2) For the dynamic online matrix vector multiplication problem, where we get an n×n matrix whose entires are drawn from a finite field of size nΘ(1), any dynamic data structure must either have an amortized update time of Ω((lgn/lglgn)2) or an amortized query time of Ω(n⋅(lgn/lglgn)2).\r\nFor these two problems, the previous works by Larsen (FOCS'12) and Clifford et al. (FOCS'15) gave the same lower bounds, but only for worst case update and query times. Our bounds match the highest unconditional lower bounds known till date for any dynamic problem in the cell-probe model." article_processing_charge: No article_type: original author: - first_name: Sayan full_name: Bhattacharya, Sayan last_name: Bhattacharya - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 - first_name: Stefan full_name: Neumann, Stefan last_name: Neumann citation: ama: Bhattacharya S, Henzinger MH, Neumann S. New amortized cell-probe lower bounds for dynamic problems. Theoretical Computer Science. 2019;779:72-87. doi:10.1016/j.tcs.2019.01.043 apa: Bhattacharya, S., Henzinger, M. H., & Neumann, S. (2019). New amortized cell-probe lower bounds for dynamic problems. Theoretical Computer Science. Elsevier. https://doi.org/10.1016/j.tcs.2019.01.043 chicago: Bhattacharya, Sayan, Monika H Henzinger, and Stefan Neumann. “New Amortized Cell-Probe Lower Bounds for Dynamic Problems.” Theoretical Computer Science. Elsevier, 2019. https://doi.org/10.1016/j.tcs.2019.01.043. ieee: S. Bhattacharya, M. H. Henzinger, and S. Neumann, “New amortized cell-probe lower bounds for dynamic problems,” Theoretical Computer Science, vol. 779. Elsevier, pp. 72–87, 2019. ista: Bhattacharya S, Henzinger MH, Neumann S. 2019. New amortized cell-probe lower bounds for dynamic problems. Theoretical Computer Science. 779, 72–87. mla: Bhattacharya, Sayan, et al. “New Amortized Cell-Probe Lower Bounds for Dynamic Problems.” Theoretical Computer Science, vol. 779, Elsevier, 2019, pp. 72–87, doi:10.1016/j.tcs.2019.01.043. short: S. Bhattacharya, M.H. Henzinger, S. Neumann, Theoretical Computer Science 779 (2019) 72–87. date_created: 2022-08-17T09:02:15Z date_published: 2019-08-02T00:00:00Z date_updated: 2022-09-09T11:29:04Z day: '02' doi: 10.1016/j.tcs.2019.01.043 extern: '1' external_id: arxiv: - '1902.02304' intvolume: ' 779' language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/1902.02304 month: '08' oa: 1 oa_version: Preprint page: 72-87 publication: Theoretical Computer Science publication_identifier: issn: - 0304-3975 publication_status: published publisher: Elsevier quality_controlled: '1' scopus_import: '1' status: public title: New amortized cell-probe lower bounds for dynamic problems type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 779 year: '2019' ...