[{"isi":1,"author":[{"last_name":"Alistarh","first_name":"Dan-Adrian","orcid":"0000-0003-3650-940X","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","full_name":"Alistarh, Dan-Adrian"},{"last_name":"Aspnes","first_name":"James","full_name":"Aspnes, James"},{"last_name":"Ellen","first_name":"Faith","full_name":"Ellen, Faith"},{"full_name":"Gelashvili, Rati","first_name":"Rati","last_name":"Gelashvili"},{"id":"a2117c59-cee4-11ed-b9d0-874ecf0f8ac5","full_name":"Zhu, Leqi","first_name":"Leqi","last_name":"Zhu"}],"external_id":{"isi":["001082972300004"],"arxiv":["1811.01421"]},"arxiv":1,"oa_version":"Preprint","related_material":{"record":[{"id":"6676","status":"public","relation":"earlier_version"}]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","acknowledgement":"We would like to thank Valerie King, Toniann Pitassi, and Michael Saks for helpful discussions and Shi Hao Liu for his useful feedback.\r\nThis research was supported by the Natural Science and Engineering Research Council of Canada under grants RGPIN-2015-05080 and RGPIN-2020-04178, a postgraduate scholarship, and a postdoctoral fellowship; a University of Toronto postdoctoral fellowship; the National Science Foundation under grants CCF-1217921, CCF-1301926, CCF-1637385, CCF-1650596, and IIS-1447786; the U.S. Department of Energy under grant ER26116/DE-SC0008923; the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme grant agreement 805223 ScaleML; and the Oracle and Intel corporations. Some of the work on this paper was done while Faith Ellen was visiting IST Austria.","department":[{"_id":"DaAl"}],"date_created":"2023-09-24T22:01:11Z","citation":{"apa":"Alistarh, D.-A., Aspnes, J., Ellen, F., Gelashvili, R., &#38; Zhu, L. (2023). Why extension-based proofs fail. <i>SIAM Journal on Computing</i>. Society for Industrial and Applied Mathematics. <a href=\"https://doi.org/10.1137/20M1375851\">https://doi.org/10.1137/20M1375851</a>","ieee":"D.-A. Alistarh, J. Aspnes, F. Ellen, R. Gelashvili, and L. Zhu, “Why extension-based proofs fail,” <i>SIAM Journal on Computing</i>, vol. 52, no. 4. Society for Industrial and Applied Mathematics, pp. 913–944, 2023.","ama":"Alistarh D-A, Aspnes J, Ellen F, Gelashvili R, Zhu L. Why extension-based proofs fail. <i>SIAM Journal on Computing</i>. 2023;52(4):913-944. doi:<a href=\"https://doi.org/10.1137/20M1375851\">10.1137/20M1375851</a>","chicago":"Alistarh, Dan-Adrian, James Aspnes, Faith Ellen, Rati Gelashvili, and Leqi Zhu. “Why Extension-Based Proofs Fail.” <i>SIAM Journal on Computing</i>. Society for Industrial and Applied Mathematics, 2023. <a href=\"https://doi.org/10.1137/20M1375851\">https://doi.org/10.1137/20M1375851</a>.","short":"D.-A. Alistarh, J. Aspnes, F. Ellen, R. Gelashvili, L. Zhu, SIAM Journal on Computing 52 (2023) 913–944.","mla":"Alistarh, Dan-Adrian, et al. “Why Extension-Based Proofs Fail.” <i>SIAM Journal on Computing</i>, vol. 52, no. 4, Society for Industrial and Applied Mathematics, 2023, pp. 913–44, doi:<a href=\"https://doi.org/10.1137/20M1375851\">10.1137/20M1375851</a>.","ista":"Alistarh D-A, Aspnes J, Ellen F, Gelashvili R, Zhu L. 2023. Why extension-based proofs fail. SIAM Journal on Computing. 52(4), 913–944."},"publisher":"Society for Industrial and Applied Mathematics","status":"public","month":"07","page":"913-944","project":[{"grant_number":"805223","_id":"268A44D6-B435-11E9-9278-68D0E5697425","name":"Elastic Coordination for Scalable Machine Learning","call_identifier":"H2020"}],"quality_controlled":"1","date_published":"2023-07-25T00:00:00Z","issue":"4","publication_identifier":{"issn":["0097-5397"],"eissn":["1095-7111"]},"intvolume":"        52","_id":"14364","ec_funded":1,"main_file_link":[{"url":"https://arxiv.org/abs/1811.01421","open_access":"1"}],"doi":"10.1137/20M1375851","publication_status":"published","day":"25","oa":1,"title":"Why extension-based proofs fail","volume":52,"year":"2023","language":[{"iso":"eng"}],"abstract":[{"lang":"eng","text":"We introduce extension-based proofs, a class of impossibility proofs that includes valency arguments. They are modelled as an interaction between a prover and a protocol. Using proofs based on combinatorial topology, it has been shown that it is impossible to deterministically solve -set agreement among  processes or approximate agreement on a cycle of length 4 among  processes in a wait-free manner in asynchronous models where processes communicate using objects that can be constructed from shared registers. However, it was unknown whether proofs based on simpler techniques were possible. We show that these impossibility results cannot be obtained by extension-based proofs in the iterated snapshot model and, hence, extension-based proofs are limited in power."}],"article_processing_charge":"No","article_type":"original","date_updated":"2025-05-14T11:26:06Z","publication":"SIAM Journal on Computing","type":"journal_article","scopus_import":"1"},{"title":"Deterministic near-optimal approximation algorithms for dynamic set cover","volume":52,"year":"2023","day":"01","abstract":[{"lang":"eng","text":"n the dynamic minimum set cover problem, the challenge is to minimize the update time while guaranteeing a close-to-optimal min{O(log n), f} approximation factor. (Throughout, n, m, f , and C are parameters denoting the maximum number of elements, the number of sets, the frequency, and the cost range.) In the high-frequency range, when f = Ω(log n) , this was achieved by a deterministic O(log n) -approximation algorithm with O(f log n) amortized update time by Gupta et al. [Online and dynamic algorithms for set cover, in Proceedings STOC 2017, ACM, pp. 537–550]. In this paper we consider the low-frequency range, when f = O(log n) , and obtain deterministic algorithms with a (1 + ∈)f -approximation ratio and the following guarantees on the update time. (1)  O ((f/∈)-log(Cn)) amortized update time: Prior to our work, the best approximation ratio guaranteed by deterministic algorithms was O(f2) of Bhattacharya, Henzinger, and Italiano [Design of dynamic algorithms via primal-dual method, in Proceedings ICALP 2015, Springer, pp. 206–218]. In contrast, the only result with O(f) -approximation was that of Abboud et al. [Dynamic set cover: Improved algorithms and lower bounds, in Proceedings STOC 2019, ACM, pp. 114–125], who designed a randomized (1+∈)f -approximation algorithm with  amortized update time. (2) O(f2/∈3 + (f/∈2).logC) amortized update time: This result improves the above update time bound for most values of f\r\n in the low-frequency range, i.e., f=o(log n) . It is also the first result that is independent of m\r\n and n. It subsumes the constant amortized update time of Bhattacharya and Kulkarni [Deterministically maintaining a (2 + ∈) -approximate minimum vertex cover in O(1/∈2) amortized update time, in Proceedings SODA 2019, SIAM, pp. 1872–1885] for unweighted dynamic vertex cover (i.e., when f = 2 and C = 1). (3) O((f/∈3).log2(Cn)) worst-case update time: No nontrivial worst-case update time was previously known for the dynamic set cover problem. Our bound subsumes and improves by a logarithmic factor the O(log3n/poly (∈)) \r\n worst-case update time for the unweighted dynamic vertex cover problem (i.e., when f = 2\r\n and C =1) of Bhattacharya, Henzinger, and Nanongkai [Fully dynamic approximate maximum matching and minimum vertex cover in O(log3)n worst case update time, in Proceedings SODA 2017, SIAM, pp. 470–489]. We achieve our results via the primal-dual approach, by maintaining a fractional packing solution as a dual certificate. Prior work in dynamic algorithms that employs the primal-dual approach uses a local update scheme that maintains relaxed complementary slackness conditions for every set. For our first result we use instead a global update scheme that does not always maintain complementary slackness conditions. For our second result we combine the global and the local update schema. To achieve our third result we use a hierarchy of background schedulers. It is an interesting open question whether this background scheduler technique can also be used to transform algorithms with amortized running time bounds into algorithms with worst-case running time bounds."}],"language":[{"iso":"eng"}],"ec_funded":1,"publication_status":"published","doi":"10.1137/21M1428649","date_updated":"2025-09-09T13:19:49Z","type":"journal_article","publication":"SIAM Journal on Computing","scopus_import":"1","article_type":"original","article_processing_charge":"No","acknowledgement":"This project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grants 715672 and\r\n101019564 ``The Design of Modern Fully Dynamic Data Structures (MoDynStruct)\"\") and from the Engineering and Physical Sciences Research Council, UK (EPSRC) under grant EP/S03353X/1. The second author was also supported by the Austrian Science Fund (FWF) project ``Fast Algorithms for a Reactive Network Layer (ReactNet),\"\" P 33775-N, with additional funding from the netidee SCIENCE Stiftung, 2020--2024, project ``Static and Dynamic Hierarchical Graph Decompositions,\"\"I 5982-N, and project Z 422-N. The third author was also supported by the Swedish Research Council (Reg. No. 2015-04659). The fourth author was also supported by the Science and Technology Development Fund (FDCT), Macau SAR (file 0014/2022/AFJ, 0085/2022/A, 0143/2020/A3, and SKL-IOTSC-2021-2023).","author":[{"last_name":"Bhattacharya","first_name":"Sayan","full_name":"Bhattacharya, Sayan"},{"last_name":"Henzinger","first_name":"Monika H","full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530"},{"full_name":"Nanongkai, Danupon","last_name":"Nanongkai","first_name":"Danupon"},{"full_name":"Wu, Xiaowei","first_name":"Xiaowei","last_name":"Wu"}],"external_id":{"isi":["001116719500002"]},"isi":1,"oa_version":"None","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","date_published":"2023-10-01T00:00:00Z","quality_controlled":"1","project":[{"_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","name":"The design and evaluation of modern fully dynamic data structures","call_identifier":"H2020","grant_number":"101019564"},{"name":"Fast Algorithms for a Reactive Network Layer","_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe","grant_number":"P33775"},{"_id":"34def286-11ca-11ed-8bc3-da5948e1613c","name":"Efficient algorithms","grant_number":"Z00422"},{"name":"Static and Dynamic Hierarchical Graph Decompositions","_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103","grant_number":"I05982"}],"issue":"5","publication_identifier":{"eissn":["1095-7111"],"issn":["0097-5397"]},"intvolume":"        52","_id":"14558","publisher":"Society for Industrial and Applied Mathematics","citation":{"ama":"Bhattacharya S, Henzinger M, Nanongkai D, Wu X. Deterministic near-optimal approximation algorithms for dynamic set cover. <i>SIAM Journal on Computing</i>. 2023;52(5):1132-1192. doi:<a href=\"https://doi.org/10.1137/21M1428649\">10.1137/21M1428649</a>","ieee":"S. Bhattacharya, M. Henzinger, D. Nanongkai, and X. Wu, “Deterministic near-optimal approximation algorithms for dynamic set cover,” <i>SIAM Journal on Computing</i>, vol. 52, no. 5. Society for Industrial and Applied Mathematics, pp. 1132–1192, 2023.","apa":"Bhattacharya, S., Henzinger, M., Nanongkai, D., &#38; Wu, X. (2023). Deterministic near-optimal approximation algorithms for dynamic set cover. <i>SIAM Journal on Computing</i>. Society for Industrial and Applied Mathematics. <a href=\"https://doi.org/10.1137/21M1428649\">https://doi.org/10.1137/21M1428649</a>","chicago":"Bhattacharya, Sayan, Monika Henzinger, Danupon Nanongkai, and Xiaowei Wu. “Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover.” <i>SIAM Journal on Computing</i>. Society for Industrial and Applied Mathematics, 2023. <a href=\"https://doi.org/10.1137/21M1428649\">https://doi.org/10.1137/21M1428649</a>.","mla":"Bhattacharya, Sayan, et al. “Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover.” <i>SIAM Journal on Computing</i>, vol. 52, no. 5, Society for Industrial and Applied Mathematics, 2023, pp. 1132–92, doi:<a href=\"https://doi.org/10.1137/21M1428649\">10.1137/21M1428649</a>.","short":"S. Bhattacharya, M. Henzinger, D. Nanongkai, X. Wu, SIAM Journal on Computing 52 (2023) 1132–1192.","ista":"Bhattacharya S, Henzinger M, Nanongkai D, Wu X. 2023. Deterministic near-optimal approximation algorithms for dynamic set cover. SIAM Journal on Computing. 52(5), 1132–1192."},"department":[{"_id":"MoHe"}],"date_created":"2023-11-19T23:00:56Z","page":"1132-1192","status":"public","month":"10"},{"acknowledgement":"Andrei Krokhin and Jakub Opršal were supported by the UK EPSRC grant EP/R034516/1. Jakub Opršal has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No 101034413. Stanislav Živný was supported by a Royal Society University Research Fellowship. This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 714532). The paper re\u001eects only the authors’ views and not the views of the ERC or the European Commission. ","keyword":["General Mathematics","General Computer Science"],"author":[{"last_name":"Krokhin","first_name":"Andrei","full_name":"Krokhin, Andrei"},{"first_name":"Jakub","last_name":"Opršal","id":"ec596741-c539-11ec-b829-c79322a91242","full_name":"Opršal, Jakub","orcid":"0000-0003-1245-3456"},{"last_name":"Wrochna","first_name":"Marcin","full_name":"Wrochna, Marcin"},{"full_name":"Živný, Stanislav","first_name":"Stanislav","last_name":"Živný"}],"external_id":{"arxiv":["2003.11351"],"isi":["000955000000001"]},"arxiv":1,"isi":1,"oa_version":"Preprint","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_published":"2023-01-01T00:00:00Z","project":[{"call_identifier":"H2020","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","name":"IST-BRIDGE: International postdoctoral program","grant_number":"101034413"}],"quality_controlled":"1","issue":"1","publication_identifier":{"issn":["0097-5397"],"eissn":["1095-7111"]},"intvolume":"        52","_id":"12563","publisher":"Society for Industrial and Applied Mathematics","citation":{"ieee":"A. Krokhin, J. Opršal, M. Wrochna, and S. Živný, “Topology and adjunction in promise constraint satisfaction,” <i>SIAM Journal on Computing</i>, vol. 52, no. 1. Society for Industrial and Applied Mathematics, pp. 38–79, 2023.","ama":"Krokhin A, Opršal J, Wrochna M, Živný S. Topology and adjunction in promise constraint satisfaction. <i>SIAM Journal on Computing</i>. 2023;52(1):38-79. doi:<a href=\"https://doi.org/10.1137/20m1378223\">10.1137/20m1378223</a>","apa":"Krokhin, A., Opršal, J., Wrochna, M., &#38; Živný, S. (2023). Topology and adjunction in promise constraint satisfaction. <i>SIAM Journal on Computing</i>. Society for Industrial and Applied Mathematics. <a href=\"https://doi.org/10.1137/20m1378223\">https://doi.org/10.1137/20m1378223</a>","mla":"Krokhin, Andrei, et al. “Topology and Adjunction in Promise Constraint Satisfaction.” <i>SIAM Journal on Computing</i>, vol. 52, no. 1, Society for Industrial and Applied Mathematics, 2023, pp. 38–79, doi:<a href=\"https://doi.org/10.1137/20m1378223\">10.1137/20m1378223</a>.","short":"A. Krokhin, J. Opršal, M. Wrochna, S. Živný, SIAM Journal on Computing 52 (2023) 38–79.","ista":"Krokhin A, Opršal J, Wrochna M, Živný S. 2023. Topology and adjunction in promise constraint satisfaction. SIAM Journal on Computing. 52(1), 38–79.","chicago":"Krokhin, Andrei, Jakub Opršal, Marcin Wrochna, and Stanislav Živný. “Topology and Adjunction in Promise Constraint Satisfaction.” <i>SIAM Journal on Computing</i>. Society for Industrial and Applied Mathematics, 2023. <a href=\"https://doi.org/10.1137/20m1378223\">https://doi.org/10.1137/20m1378223</a>."},"department":[{"_id":"UlWa"}],"date_created":"2023-02-16T07:03:52Z","page":"38-79","status":"public","month":"01","title":"Topology and adjunction in promise constraint satisfaction","volume":52,"year":"2023","day":"01","oa":1,"abstract":[{"text":"he approximate graph coloring problem, whose complexity is unresolved in most cases, concerns finding a c-coloring of a graph that is promised to be k-colorable, where c≥k. This problem naturally generalizes to promise graph homomorphism problems and further to promise constraint satisfaction problems. The complexity of these problems has recently been studied through an algebraic approach. In this paper, we introduce two new techniques to analyze the complexity of promise CSPs: one is based on topology and the other on adjunction. We apply these techniques, together with the previously introduced algebraic approach, to obtain new unconditional NP-hardness results for a significant class of approximate graph coloring and promise graph homomorphism problems.","lang":"eng"}],"language":[{"iso":"eng"}],"ec_funded":1,"main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2003.11351"}],"publication_status":"published","doi":"10.1137/20m1378223","date_updated":"2025-05-14T10:51:32Z","type":"journal_article","publication":"SIAM Journal on Computing","scopus_import":"1","article_type":"original","article_processing_charge":"No"},{"_id":"12960","intvolume":"        52","issue":"2","publication_identifier":{"eissn":["1095-7111"],"issn":["0097-5397"]},"date_published":"2023-04-30T00:00:00Z","quality_controlled":"1","project":[{"call_identifier":"H2020","name":"ISTplus - Postdoctoral Fellowships","_id":"260C2330-B435-11E9-9278-68D0E5697425","grant_number":"754411"},{"grant_number":"M03073","name":"Learning and triangulating manifolds via collapses","_id":"fc390959-9c52-11eb-aca3-afa58bd282b2"}],"page":"452-486","month":"04","status":"public","publisher":"Society for Industrial and Applied Mathematics","citation":{"ista":"Boissonnat JD, Kachanovich S, Wintraecken M. 2023. Tracing isomanifolds in Rd in time polynomial in d using Coxeter–Freudenthal–Kuhn triangulations. SIAM Journal on Computing. 52(2), 452–486.","short":"J.D. Boissonnat, S. Kachanovich, M. Wintraecken, SIAM Journal on Computing 52 (2023) 452–486.","mla":"Boissonnat, Jean Daniel, et al. “Tracing Isomanifolds in Rd in Time Polynomial in d Using Coxeter–Freudenthal–Kuhn Triangulations.” <i>SIAM Journal on Computing</i>, vol. 52, no. 2, Society for Industrial and Applied Mathematics, 2023, pp. 452–86, doi:<a href=\"https://doi.org/10.1137/21M1412918\">10.1137/21M1412918</a>.","chicago":"Boissonnat, Jean Daniel, Siargey Kachanovich, and Mathijs Wintraecken. “Tracing Isomanifolds in Rd in Time Polynomial in d Using Coxeter–Freudenthal–Kuhn Triangulations.” <i>SIAM Journal on Computing</i>. Society for Industrial and Applied Mathematics, 2023. <a href=\"https://doi.org/10.1137/21M1412918\">https://doi.org/10.1137/21M1412918</a>.","ieee":"J. D. Boissonnat, S. Kachanovich, and M. Wintraecken, “Tracing isomanifolds in Rd in time polynomial in d using Coxeter–Freudenthal–Kuhn triangulations,” <i>SIAM Journal on Computing</i>, vol. 52, no. 2. Society for Industrial and Applied Mathematics, pp. 452–486, 2023.","apa":"Boissonnat, J. D., Kachanovich, S., &#38; Wintraecken, M. (2023). Tracing isomanifolds in Rd in time polynomial in d using Coxeter–Freudenthal–Kuhn triangulations. <i>SIAM Journal on Computing</i>. Society for Industrial and Applied Mathematics. <a href=\"https://doi.org/10.1137/21M1412918\">https://doi.org/10.1137/21M1412918</a>","ama":"Boissonnat JD, Kachanovich S, Wintraecken M. Tracing isomanifolds in Rd in time polynomial in d using Coxeter–Freudenthal–Kuhn triangulations. <i>SIAM Journal on Computing</i>. 2023;52(2):452-486. doi:<a href=\"https://doi.org/10.1137/21M1412918\">10.1137/21M1412918</a>"},"department":[{"_id":"HeEd"}],"date_created":"2023-05-14T22:01:00Z","acknowledgement":"The authors have received funding from the European Research Council under the European Union's ERC grant greement 339025 GUDHI (Algorithmic Foundations of Geometric Un-derstanding  in  Higher  Dimensions).   The  first  author  was  supported  by  the  French  government,through the 3IA C\\^ote d'Azur Investments in the Future project managed by the National ResearchAgency (ANR) with the reference ANR-19-P3IA-0002.  The third author was supported by the Eu-ropean Union's Horizon 2020 research and innovation programme under the Marie Sk\\lodowska-Curiegrant agreement 754411 and the FWF (Austrian Science Fund) grant M 3073.","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","related_material":{"record":[{"relation":"earlier_version","id":"9441","status":"public"}]},"oa_version":"Submitted Version","external_id":{"isi":["001013183000012"]},"author":[{"last_name":"Boissonnat","first_name":"Jean Daniel","full_name":"Boissonnat, Jean Daniel"},{"full_name":"Kachanovich, Siargey","first_name":"Siargey","last_name":"Kachanovich"},{"last_name":"Wintraecken","first_name":"Mathijs","full_name":"Wintraecken, Mathijs","id":"307CFBC8-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-7472-2220"}],"isi":1,"scopus_import":"1","publication":"SIAM Journal on Computing","type":"journal_article","date_updated":"2025-04-15T06:54:46Z","article_type":"original","article_processing_charge":"No","corr_author":"1","abstract":[{"lang":"eng","text":"Isomanifolds are the generalization of isosurfaces to arbitrary dimension and codimension, i.e., submanifolds of Rd defined as the zero set of some multivariate multivalued smooth function f:Rd→Rd−n, where n is the intrinsic dimension of the manifold. A natural way to approximate a smooth isomanifold M=f−1(0) is to consider its piecewise linear (PL) approximation M^\r\n based on a triangulation T of the ambient space Rd. In this paper, we describe a simple algorithm to trace isomanifolds from a given starting point. The algorithm works for arbitrary dimensions n and d, and any precision D. Our main result is that, when f (or M) has bounded complexity, the complexity of the algorithm is polynomial in d and δ=1/D (and unavoidably exponential in n). Since it is known that for δ=Ω(d2.5), M^ is O(D2)-close and isotopic to M\r\n, our algorithm produces a faithful PL-approximation of isomanifolds of bounded complexity in time polynomial in d. Combining this algorithm with dimensionality reduction techniques, the dependency on d in the size of M^ can be completely removed with high probability. We also show that the algorithm can handle isomanifolds with boundary and, more generally, isostratifolds. The algorithm for isomanifolds with boundary has been implemented and experimental results are reported, showing that it is practical and can handle cases that are far ahead of the state-of-the-art. "}],"language":[{"iso":"eng"}],"year":"2023","volume":52,"title":"Tracing isomanifolds in Rd in time polynomial in d using Coxeter–Freudenthal–Kuhn triangulations","oa":1,"day":"30","publication_status":"published","doi":"10.1137/21M1412918","main_file_link":[{"url":"https://hal-emse.ccsd.cnrs.fr/3IA-COTEDAZUR/hal-04083489v1","open_access":"1"}],"ec_funded":1},{"doi":"10.1137/16m1097808","publication_status":"published","main_file_link":[{"url":"https://arxiv.org/abs/1504.07056","open_access":"1"}],"language":[{"iso":"eng"}],"abstract":[{"lang":"eng","text":"We present a deterministic (1+𝑜(1))-approximation (𝑛1/2+𝑜(1)+𝐷1+𝑜(1))-time algorithm for solving the single-source shortest paths problem on distributed weighted networks (the \\sf CONGEST model); here 𝑛 is the number of nodes in the network, 𝐷 is its (hop) diameter, and edge weights are positive integers from 1 to poly(𝑛). This is the first nontrivial deterministic algorithm for this problem. It also improves (i) the running time of the randomized (1+𝑜(1))-approximation 𝑂̃ (𝑛√𝐷1/4+𝐷)-time algorithm of Nanongkai [in Proceedings of STOC, 2014, pp. 565--573] by a factor of as large as 𝑛1/8, and (ii) the 𝑂(𝜖−1log𝜖−1)-approximation factor of Lenzen and Patt-Shamir's 𝑂̃ (𝑛1/2+𝜖+𝐷)-time algorithm [in Proceedings of STOC, 2013, pp. 381--390] within the same running time. (Throughout, we use 𝑂̃ (⋅) to hide polylogarithmic factors in 𝑛.) Our running time matches the known time lower bound of Ω(𝑛/log𝑛‾‾‾‾‾‾‾√+𝐷) [M. Elkin, SIAM J. Comput., 36 (2006), pp. 433--456], thus essentially settling the status of this problem which was raised at least a decade ago [M. Elkin, SIGACT News, 35 (2004), pp. 40--57]. It also implies a (2+𝑜(1))-approximation (𝑛1/2+𝑜(1)+𝐷1+𝑜(1))-time algorithm for approximating a network's weighted diameter which almost matches the lower bound by Holzer and Pinsker [in Proceedings of OPODIS, 2015, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, Germany, 2016, 6]. In 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 (𝑛𝑜(1),𝑜(1))-hop set of size 𝑛1+𝑜(1). We combine these techniques with many distributed algorithmic techniques, some of which are from problems that are not directly related to shortest paths, e.g., ruling sets [A. V. Goldberg, S. A. Plotkin, and G. E. Shannon, SIAM J. Discrete Math., 1 (1988), pp. 434--446], source detection [C. Lenzen and D. Peleg, in Proceedings of PODC, 2013, pp. 375--382], and partial distance estimation [C. Lenzen and B. Patt-Shamir, in Proceedings of PODC, 2015, pp. 153--162]. Our hop set construction also leads to single-source shortest paths algorithms in two other settings: (i) a (1+𝑜(1))-approximation 𝑛𝑜(1)-time algorithm on congested cliques, and (ii) a (1+𝑜(1))-approximation 𝑛𝑜(1)-pass 𝑛1+𝑜(1)-space streaming algorithm. The first result answers an open problem in [D. Nanongkai, in Proceedings of STOC, 2014, pp. 565--573]. The second result partially answers an open problem raised by McGregor in 2006 [List of Open Problems in Sublinear Algorithms: Problem 14]."}],"extern":"1","oa":1,"day":"01","year":"2021","title":"A deterministic almost-tight distributed algorithm for approximating single-source shortest paths","volume":50,"article_processing_charge":"No","article_type":"original","scopus_import":"1","publication":"SIAM Journal on Computing","type":"journal_article","date_updated":"2024-11-06T12:22:31Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Preprint","arxiv":1,"external_id":{"arxiv":["1504.07056"]},"author":[{"last_name":"Henzinger","first_name":"Monika H","full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530"},{"last_name":"Krinninger","first_name":"Sebastian","full_name":"Krinninger, Sebastian"},{"full_name":"Nanongkai, Danupon","last_name":"Nanongkai","first_name":"Danupon"}],"month":"05","status":"public","page":"STOC16-98-STOC16-137","date_created":"2022-08-17T07:54:45Z","publisher":"Society for Industrial & Applied Mathematics","citation":{"apa":"Henzinger, M., Krinninger, S., &#38; Nanongkai, D. (2021). A deterministic almost-tight distributed algorithm for approximating single-source shortest paths. <i>SIAM Journal on Computing</i>. Society for Industrial &#38; Applied Mathematics. <a href=\"https://doi.org/10.1137/16m1097808\">https://doi.org/10.1137/16m1097808</a>","ama":"Henzinger M, Krinninger S, Nanongkai D. A deterministic almost-tight distributed algorithm for approximating single-source shortest paths. <i>SIAM Journal on Computing</i>. 2021;50(3):STOC16-98-STOC16-137. doi:<a href=\"https://doi.org/10.1137/16m1097808\">10.1137/16m1097808</a>","ieee":"M. Henzinger, S. Krinninger, and D. Nanongkai, “A deterministic almost-tight distributed algorithm for approximating single-source shortest paths,” <i>SIAM Journal on Computing</i>, vol. 50, no. 3. Society for Industrial &#38; Applied Mathematics, pp. STOC16-98-STOC16-137, 2021.","chicago":"Henzinger, Monika, Sebastian Krinninger, and Danupon Nanongkai. “A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths.” <i>SIAM Journal on Computing</i>. Society for Industrial &#38; Applied Mathematics, 2021. <a href=\"https://doi.org/10.1137/16m1097808\">https://doi.org/10.1137/16m1097808</a>.","short":"M. Henzinger, S. Krinninger, D. Nanongkai, SIAM Journal on Computing 50 (2021) STOC16-98-STOC16-137.","mla":"Henzinger, Monika, et al. “A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths.” <i>SIAM Journal on Computing</i>, vol. 50, no. 3, Society for Industrial &#38; Applied Mathematics, 2021, pp. STOC16-98-STOC16-137, doi:<a href=\"https://doi.org/10.1137/16m1097808\">10.1137/16m1097808</a>.","ista":"Henzinger M, Krinninger S, Nanongkai D. 2021. A deterministic almost-tight distributed algorithm for approximating single-source shortest paths. SIAM Journal on Computing. 50(3), STOC16-98-STOC16-137."},"_id":"11886","issue":"3","intvolume":"        50","publication_identifier":{"issn":["0097-5397"],"eissn":["1095-7111"]},"quality_controlled":"1","date_published":"2021-05-01T00:00:00Z"},{"article_processing_charge":"No","article_type":"original","scopus_import":"1","publication":"SIAM Journal on Computing","type":"journal_article","date_updated":"2025-09-10T10:14:11Z","doi":"10.1137/20m1366502","publication_status":"published","ec_funded":1,"language":[{"iso":"eng"}],"abstract":[{"lang":"eng","text":"We settle the complexity of the (∆ + 1)-coloring and (∆ + 1)-list coloring problems intheCONGESTED CLIQUEmodel by presenting a simpledeterministicalgorithm for both problemsrunning in a constant number of rounds.  This matches the complexity of the recent breakthroughrandomizedconstant-round (∆ + 1)-list coloring algorithm due to Chang et al.  [Proceedings of the38th  ACM  Symposium  on  Principles  of  Distributed  Computing,  2019]  and  significantly  improvesupon the state-of-the-artO(log ∆)-round deterministic (∆ + 1)-coloring bound of Parter [Proceed-ings of the 45th Annual International Colloquium on Automata, Languages and Programming].  Aremarkable property of our algorithm is its simplicity.  Whereas the state-of-the-artrandomizedal-gorithms for this problem are based on the quite involved local coloring algorithm of Chang, Li, andPettie [Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018],our algorithm can be described in just a few lines.  At a high level, it applies a careful derandomiza-tion of a recursive procedure which partitions the nodes and their respective palettes into separatebins.  We show that afterO(1) recursion steps, the remaining uncolored subgraph within each bin haslinear size and thus can be solved locally by collecting it to a single node.  This algorithm can alsobe implemented in the massively parallel computation (MPC) model provided that each machine haslinear (inn, the number of nodes in the input graph) space.  We also show an extension of our algo-rithm to theMPCregime, in which machines havesublinearspace:  we present the first deterministic(∆ + 1)-list coloring algorithm designed for sublinear-spaceMPC, which runs inO(log ∆ + log logn)rounds."}],"day":"01","year":"2021","volume":50,"title":"Simple, deterministic, constant-round coloring in congested clique and MPC","month":"01","status":"public","page":"1603-1626","date_created":"2024-04-03T07:53:22Z","department":[{"_id":"DaAl"}],"citation":{"ama":"Czumaj A, Davies P, Parter M. Simple, deterministic, constant-round coloring in congested clique and MPC. <i>SIAM Journal on Computing</i>. 2021;50(5):1603-1626. doi:<a href=\"https://doi.org/10.1137/20m1366502\">10.1137/20m1366502</a>","ieee":"A. Czumaj, P. Davies, and M. Parter, “Simple, deterministic, constant-round coloring in congested clique and MPC,” <i>SIAM Journal on Computing</i>, vol. 50, no. 5. Society for Industrial and Applied Mathematics, pp. 1603–1626, 2021.","apa":"Czumaj, A., Davies, P., &#38; Parter, M. (2021). Simple, deterministic, constant-round coloring in congested clique and MPC. <i>SIAM Journal on Computing</i>. Society for Industrial and Applied Mathematics. <a href=\"https://doi.org/10.1137/20m1366502\">https://doi.org/10.1137/20m1366502</a>","ista":"Czumaj A, Davies P, Parter M. 2021. Simple, deterministic, constant-round coloring in congested clique and MPC. SIAM Journal on Computing. 50(5), 1603–1626.","mla":"Czumaj, Artur, et al. “Simple, Deterministic, Constant-Round Coloring in Congested Clique and MPC.” <i>SIAM Journal on Computing</i>, vol. 50, no. 5, Society for Industrial and Applied Mathematics, 2021, pp. 1603–26, doi:<a href=\"https://doi.org/10.1137/20m1366502\">10.1137/20m1366502</a>.","short":"A. Czumaj, P. Davies, M. Parter, SIAM Journal on Computing 50 (2021) 1603–1626.","chicago":"Czumaj, Artur, Peter Davies, and Merav Parter. “Simple, Deterministic, Constant-Round Coloring in Congested Clique and MPC.” <i>SIAM Journal on Computing</i>. Society for Industrial and Applied Mathematics, 2021. <a href=\"https://doi.org/10.1137/20m1366502\">https://doi.org/10.1137/20m1366502</a>."},"publisher":"Society for Industrial and Applied Mathematics","_id":"15271","intvolume":"        50","publication_identifier":{"eissn":["1095-7111"],"issn":["0097-5397"]},"issue":"5","project":[{"call_identifier":"H2020","_id":"260C2330-B435-11E9-9278-68D0E5697425","name":"ISTplus - Postdoctoral Fellowships","grant_number":"754411"}],"quality_controlled":"1","date_published":"2021-01-01T00:00:00Z","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","oa_version":"None","isi":1,"external_id":{"isi":["000713008600004"]},"author":[{"full_name":"Czumaj, Artur","last_name":"Czumaj","first_name":"Artur"},{"orcid":"0000-0002-5646-9524","id":"11396234-BB50-11E9-B24C-90FCE5697425","full_name":"Davies, Peter","first_name":"Peter","last_name":"Davies"},{"full_name":"Parter, Merav","last_name":"Parter","first_name":"Merav"}],"keyword":["General Mathematics","General Computer Science"],"acknowledgement":"The  first  author  was  partially  supported  by  the  Centre  for  Discrete  Mathematics and its Applications, by the IBM Faculty Award, and by the EPSRC award EP/N011163/1.  The second author was partially supported by the European Union’s Horizon 2020 research and innovation program under the Marie Sklodowska-Curie grant agreement 754411.  The first and third authors were partially supported by a Weizmann-UK Making Connections grant."},{"scopus_import":"1","date_updated":"2024-11-06T12:22:42Z","type":"journal_article","publication":"SIAM Journal on Computing","article_type":"original","article_processing_charge":"No","abstract":[{"text":"We study the problem of computing a minimum cut in a simple, undirected graph and give a deterministic 𝑂(𝑚log2𝑛loglog2𝑛) time algorithm. This improves on both the best previously known deterministic running time of 𝑂(𝑚log12𝑛) (Kawarabayashi and Thorup [J. ACM, 66 (2018), 4]) and the best previously known randomized running time of 𝑂(𝑚log3𝑛) (Karger [J. ACM, 47 (2000), pp. 46--76]) for this problem, though Karger's algorithm can be further applied to weighted graphs. Moreover, our result extends to balanced directed graphs, where the balance of a directed graph captures how close the graph is to being Eulerian. Our approach is using the Kawarabayashi and Thorup graph compression technique, which repeatedly finds low conductance cuts. To find these cuts they use a diffusion-based local algorithm. We use instead a flow-based local algorithm and suitably adjust their framework to work with our flow-based subroutine. Both flow- and diffusion-based methods have a long history of being applied to finding low conductance cuts. Diffusion algorithms have several variants that are naturally local, while it is more complicated to make flow methods local. Some prior work has proven nice properties for local flow-based algorithms with respect to improving or cleaning up low conductance cuts. Our flow subroutine, however, is the first that both is local and produces low conductance cuts. Thus, it may be of independent interest.","lang":"eng"}],"language":[{"iso":"eng"}],"title":"Local flow partitioning for faster edge connectivity","volume":49,"year":"2020","day":"01","extern":"1","publication_status":"published","doi":"10.1137/18m1180335","main_file_link":[{"url":"https://arxiv.org/abs/1704.01254"}],"publication_identifier":{"eissn":["1095-7111"],"issn":["0097-5397"]},"issue":"1","intvolume":"        49","_id":"11889","date_published":"2020-01-01T00:00:00Z","quality_controlled":"1","page":"1-36","status":"public","month":"01","publisher":"Society for Industrial & Applied Mathematics","citation":{"ista":"Henzinger M, Rao S, Wang D. 2020. Local flow partitioning for faster edge connectivity. SIAM Journal on Computing. 49(1), 1–36.","mla":"Henzinger, Monika, et al. “Local Flow Partitioning for Faster Edge Connectivity.” <i>SIAM Journal on Computing</i>, vol. 49, no. 1, Society for Industrial &#38; Applied Mathematics, 2020, pp. 1–36, doi:<a href=\"https://doi.org/10.1137/18m1180335\">10.1137/18m1180335</a>.","short":"M. Henzinger, S. Rao, D. Wang, SIAM Journal on Computing 49 (2020) 1–36.","chicago":"Henzinger, Monika, Satish Rao, and Di Wang. “Local Flow Partitioning for Faster Edge Connectivity.” <i>SIAM Journal on Computing</i>. Society for Industrial &#38; Applied Mathematics, 2020. <a href=\"https://doi.org/10.1137/18m1180335\">https://doi.org/10.1137/18m1180335</a>.","ama":"Henzinger M, Rao S, Wang D. Local flow partitioning for faster edge connectivity. <i>SIAM Journal on Computing</i>. 2020;49(1):1-36. doi:<a href=\"https://doi.org/10.1137/18m1180335\">10.1137/18m1180335</a>","ieee":"M. Henzinger, S. Rao, and D. Wang, “Local flow partitioning for faster edge connectivity,” <i>SIAM Journal on Computing</i>, vol. 49, no. 1. Society for Industrial &#38; Applied Mathematics, pp. 1–36, 2020.","apa":"Henzinger, M., Rao, S., &#38; Wang, D. (2020). Local flow partitioning for faster edge connectivity. <i>SIAM Journal on Computing</i>. Society for Industrial &#38; Applied Mathematics. <a href=\"https://doi.org/10.1137/18m1180335\">https://doi.org/10.1137/18m1180335</a>"},"date_created":"2022-08-17T08:09:31Z","oa_version":"Preprint","related_material":{"record":[{"relation":"later_version","status":"public","id":"11873"}]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger","first_name":"Monika H"},{"full_name":"Rao, Satish","first_name":"Satish","last_name":"Rao"},{"full_name":"Wang, Di","last_name":"Wang","first_name":"Di"}],"arxiv":1,"external_id":{"arxiv":["1704.01254"]}},{"_id":"6672","publication_identifier":{"eissn":["1095-7111"],"issn":["0097-5397"]},"issue":"3","intvolume":"        48","date_published":"2019-05-21T00:00:00Z","quality_controlled":"1","page":"1046-1097","month":"05","status":"public","citation":{"chicago":"Boissonnat, Jean-Daniel, Mael Rouxel-Labbé, and Mathijs Wintraecken. “Anisotropic Triangulations via Discrete Riemannian Voronoi Diagrams.” <i>SIAM Journal on Computing</i>. Society for Industrial &#38; Applied Mathematics (SIAM), 2019. <a href=\"https://doi.org/10.1137/17m1152292\">https://doi.org/10.1137/17m1152292</a>.","short":"J.-D. Boissonnat, M. Rouxel-Labbé, M. Wintraecken, SIAM Journal on Computing 48 (2019) 1046–1097.","mla":"Boissonnat, Jean-Daniel, et al. “Anisotropic Triangulations via Discrete Riemannian Voronoi Diagrams.” <i>SIAM Journal on Computing</i>, vol. 48, no. 3, Society for Industrial &#38; Applied Mathematics (SIAM), 2019, pp. 1046–97, doi:<a href=\"https://doi.org/10.1137/17m1152292\">10.1137/17m1152292</a>.","ista":"Boissonnat J-D, Rouxel-Labbé M, Wintraecken M. 2019. Anisotropic triangulations via discrete Riemannian Voronoi diagrams. SIAM Journal on Computing. 48(3), 1046–1097.","ama":"Boissonnat J-D, Rouxel-Labbé M, Wintraecken M. Anisotropic triangulations via discrete Riemannian Voronoi diagrams. <i>SIAM Journal on Computing</i>. 2019;48(3):1046-1097. doi:<a href=\"https://doi.org/10.1137/17m1152292\">10.1137/17m1152292</a>","apa":"Boissonnat, J.-D., Rouxel-Labbé, M., &#38; Wintraecken, M. (2019). Anisotropic triangulations via discrete Riemannian Voronoi diagrams. <i>SIAM Journal on Computing</i>. Society for Industrial &#38; Applied Mathematics (SIAM). <a href=\"https://doi.org/10.1137/17m1152292\">https://doi.org/10.1137/17m1152292</a>","ieee":"J.-D. Boissonnat, M. Rouxel-Labbé, and M. Wintraecken, “Anisotropic triangulations via discrete Riemannian Voronoi diagrams,” <i>SIAM Journal on Computing</i>, vol. 48, no. 3. Society for Industrial &#38; Applied Mathematics (SIAM), pp. 1046–1097, 2019."},"publisher":"Society for Industrial & Applied Mathematics (SIAM)","date_created":"2019-07-24T08:42:12Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Preprint","arxiv":1,"external_id":{"arxiv":["1703.06487"]},"author":[{"full_name":"Boissonnat, Jean-Daniel","first_name":"Jean-Daniel","last_name":"Boissonnat"},{"full_name":"Rouxel-Labbé, Mael","first_name":"Mael","last_name":"Rouxel-Labbé"},{"orcid":"0000-0002-7472-2220","full_name":"Wintraecken, Mathijs","id":"307CFBC8-F248-11E8-B48F-1D18A9856A87","first_name":"Mathijs","last_name":"Wintraecken"}],"publication":"SIAM Journal on Computing","type":"journal_article","date_updated":"2021-01-12T08:08:30Z","abstract":[{"text":"The construction of anisotropic triangulations is desirable for various applications, such as the numerical solving of partial differential equations and the representation of surfaces in graphics. To solve this notoriously difficult problem in a practical way, we introduce the discrete Riemannian Voronoi diagram, a discrete structure that approximates the Riemannian Voronoi diagram. This structure has been implemented and was shown to lead to good triangulations in $\\mathbb{R}^2$ and on surfaces embedded in $\\mathbb{R}^3$ as detailed in our experimental companion paper. In this paper, we study theoretical aspects of our structure. Given a finite set of points $\\mathcal{P}$ in a domain $\\Omega$ equipped with a Riemannian metric, we compare the discrete Riemannian Voronoi diagram of $\\mathcal{P}$ to its Riemannian Voronoi diagram. Both diagrams have dual structures called the discrete Riemannian Delaunay and the Riemannian Delaunay complex. We provide conditions that guarantee that these dual structures are identical. It then follows from previous results that the discrete Riemannian Delaunay complex can be embedded in $\\Omega$ under sufficient conditions, leading to an anisotropic triangulation with curved simplices. Furthermore, we show that, under similar conditions, the simplices of this triangulation can be straightened.","lang":"eng"}],"language":[{"iso":"eng"}],"year":"2019","title":"Anisotropic triangulations via discrete Riemannian Voronoi diagrams","volume":48,"extern":"1","oa":1,"day":"21","publication_status":"published","doi":"10.1137/17m1152292","main_file_link":[{"url":"https://arxiv.org/abs/1703.06487","open_access":"1"}]},{"_id":"7412","intvolume":"        48","publication_identifier":{"issn":["0097-5397"],"eissn":["1095-7111"]},"issue":"5","project":[{"grant_number":"616160","call_identifier":"FP7","_id":"25FBA906-B435-11E9-9278-68D0E5697425","name":"Discrete Optimization in Computer Vision: Theory and Practice"}],"quality_controlled":"1","date_published":"2019-10-31T00:00:00Z","month":"10","status":"public","page":"1583-1602","date_created":"2020-01-30T09:27:32Z","department":[{"_id":"VlKo"}],"publisher":"SIAM","citation":{"chicago":"Achlioptas, Dimitris, Fotis Iliopoulos, and Vladimir Kolmogorov. “A Local Lemma for Focused Stochastical Algorithms.” <i>SIAM Journal on Computing</i>. SIAM, 2019. <a href=\"https://doi.org/10.1137/16m109332x\">https://doi.org/10.1137/16m109332x</a>.","short":"D. Achlioptas, F. Iliopoulos, V. Kolmogorov, SIAM Journal on Computing 48 (2019) 1583–1602.","mla":"Achlioptas, Dimitris, et al. “A Local Lemma for Focused Stochastical Algorithms.” <i>SIAM Journal on Computing</i>, vol. 48, no. 5, SIAM, 2019, pp. 1583–602, doi:<a href=\"https://doi.org/10.1137/16m109332x\">10.1137/16m109332x</a>.","ista":"Achlioptas D, Iliopoulos F, Kolmogorov V. 2019. A local lemma for focused stochastical algorithms. SIAM Journal on Computing. 48(5), 1583–1602.","apa":"Achlioptas, D., Iliopoulos, F., &#38; Kolmogorov, V. (2019). A local lemma for focused stochastical algorithms. <i>SIAM Journal on Computing</i>. SIAM. <a href=\"https://doi.org/10.1137/16m109332x\">https://doi.org/10.1137/16m109332x</a>","ama":"Achlioptas D, Iliopoulos F, Kolmogorov V. A local lemma for focused stochastical algorithms. <i>SIAM Journal on Computing</i>. 2019;48(5):1583-1602. doi:<a href=\"https://doi.org/10.1137/16m109332x\">10.1137/16m109332x</a>","ieee":"D. Achlioptas, F. Iliopoulos, and V. Kolmogorov, “A local lemma for focused stochastical algorithms,” <i>SIAM Journal on Computing</i>, vol. 48, no. 5. SIAM, pp. 1583–1602, 2019."},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","oa_version":"Preprint","isi":1,"arxiv":1,"external_id":{"arxiv":["1809.01537"],"isi":["000493900200005"]},"author":[{"full_name":"Achlioptas, Dimitris","first_name":"Dimitris","last_name":"Achlioptas"},{"first_name":"Fotis","last_name":"Iliopoulos","full_name":"Iliopoulos, Fotis"},{"first_name":"Vladimir","last_name":"Kolmogorov","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","full_name":"Kolmogorov, Vladimir"}],"scopus_import":"1","publication":"SIAM Journal on Computing","type":"journal_article","date_updated":"2024-11-04T13:52:36Z","article_processing_charge":"No","article_type":"original","language":[{"iso":"eng"}],"abstract":[{"lang":"eng","text":"We develop a framework for the rigorous analysis of focused stochastic local search algorithms. These algorithms search a state space by repeatedly selecting some constraint that is violated in the current state and moving to a random nearby state that addresses the violation, while (we hope) not introducing many new violations. An important class of focused local search algorithms with provable performance guarantees has recently arisen from algorithmizations of the Lovász local lemma (LLL), a nonconstructive tool for proving the existence of satisfying states by introducing a background measure on the state space. While powerful, the state transitions of algorithms in this class must be, in a precise sense, perfectly compatible with the background measure. In many applications this is a very restrictive requirement, and one needs to step outside the class. Here we introduce the notion of measure distortion and develop a framework for analyzing arbitrary focused stochastic local search algorithms, recovering LLL algorithmizations as the special case of no distortion. Our framework takes as input an arbitrary algorithm of such type and an arbitrary probability measure and shows how to use the measure as a yardstick of algorithmic progress, even for algorithms designed independently of the measure."}],"oa":1,"day":"31","year":"2019","volume":48,"title":"A local lemma for focused stochastical algorithms","doi":"10.1137/16m109332x","publication_status":"published","ec_funded":1,"main_file_link":[{"url":"https://arxiv.org/abs/1809.01537","open_access":"1"}]},{"publication":"SIAM Journal on Computing","type":"journal_article","date_updated":"2024-11-06T12:22:54Z","scopus_import":"1","article_type":"original","article_processing_charge":"No","year":"2018","title":"Deterministic fully dynamic data structures for vertex cover and matching","volume":47,"extern":"1","oa":1,"day":"01","abstract":[{"text":"We present the first deterministic data structures for maintaining approximate minimum vertex cover and maximum matching in a fully dynamic graph 𝐺=(𝑉,𝐸), with |𝑉|=𝑛 and |𝐸|=𝑚, in 𝑜(𝑚‾‾√) time per update. In particular, for minimum vertex cover, we provide deterministic data structures for maintaining a (2+𝜖) approximation in 𝑂(log𝑛/𝜖2) amortized time per update. For maximum matching, we show how to maintain a (3+𝜖) approximation in 𝑂(min(𝑛√/𝜖,𝑚1/3/𝜖2) amortized time per update and a (4+𝜖) approximation in 𝑂(𝑚1/3/𝜖2) worst-case time per update. Our data structure for fully dynamic minimum vertex cover is essentially near-optimal and settles an open problem by Onak and Rubinfeld [in 42nd ACM Symposium on Theory of Computing, Cambridge, MA, ACM, 2010, pp. 457--464].","lang":"eng"}],"language":[{"iso":"eng"}],"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1412.1318"}],"publication_status":"published","doi":"10.1137/140998925","date_published":"2018-05-01T00:00:00Z","quality_controlled":"1","_id":"11890","issue":"3","publication_identifier":{"eissn":["1095-7111"],"issn":["0097-5397"]},"intvolume":"        47","citation":{"ama":"Bhattacharya S, Henzinger M, Italiano GF. Deterministic fully dynamic data structures for vertex cover and matching. <i>SIAM Journal on Computing</i>. 2018;47(3):859-887. doi:<a href=\"https://doi.org/10.1137/140998925\">10.1137/140998925</a>","ieee":"S. Bhattacharya, M. Henzinger, and G. F. Italiano, “Deterministic fully dynamic data structures for vertex cover and matching,” <i>SIAM Journal on Computing</i>, vol. 47, no. 3. Society for Industrial &#38; Applied Mathematics, pp. 859–887, 2018.","apa":"Bhattacharya, S., Henzinger, M., &#38; Italiano, G. F. (2018). Deterministic fully dynamic data structures for vertex cover and matching. <i>SIAM Journal on Computing</i>. Society for Industrial &#38; Applied Mathematics. <a href=\"https://doi.org/10.1137/140998925\">https://doi.org/10.1137/140998925</a>","chicago":"Bhattacharya, Sayan, Monika Henzinger, and Giuseppe F. Italiano. “Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching.” <i>SIAM Journal on Computing</i>. Society for Industrial &#38; Applied Mathematics, 2018. <a href=\"https://doi.org/10.1137/140998925\">https://doi.org/10.1137/140998925</a>.","mla":"Bhattacharya, Sayan, et al. “Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching.” <i>SIAM Journal on Computing</i>, vol. 47, no. 3, Society for Industrial &#38; Applied Mathematics, 2018, pp. 859–87, doi:<a href=\"https://doi.org/10.1137/140998925\">10.1137/140998925</a>.","short":"S. Bhattacharya, M. Henzinger, G.F. Italiano, SIAM Journal on Computing 47 (2018) 859–887.","ista":"Bhattacharya S, Henzinger M, Italiano GF. 2018. Deterministic fully dynamic data structures for vertex cover and matching. SIAM Journal on Computing. 47(3), 859–887."},"publisher":"Society for Industrial & Applied Mathematics","date_created":"2022-08-17T08:21:23Z","page":"859-887","month":"05","status":"public","external_id":{"arxiv":["1412.1318"]},"arxiv":1,"author":[{"full_name":"Bhattacharya, Sayan","first_name":"Sayan","last_name":"Bhattacharya"},{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","last_name":"Henzinger","first_name":"Monika H"},{"full_name":"Italiano, Giuseppe F.","last_name":"Italiano","first_name":"Giuseppe F."}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Preprint","related_material":{"record":[{"relation":"earlier_version","id":"11875","status":"public"}]}},{"isi":1,"external_id":{"isi":["000453785100001"],"arxiv":["1506.08547"]},"arxiv":1,"author":[{"full_name":"Kolmogorov, Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","last_name":"Kolmogorov","first_name":"Vladimir"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Preprint","related_material":{"record":[{"relation":"earlier_version","status":"public","id":"1193"}]},"quality_controlled":"1","project":[{"grant_number":"616160","_id":"25FBA906-B435-11E9-9278-68D0E5697425","name":"Discrete Optimization in Computer Vision: Theory and Practice","call_identifier":"FP7"}],"date_published":"2018-11-08T00:00:00Z","_id":"5975","issue":"6","publication_identifier":{"eissn":["1095-7111"],"issn":["0097-5397"]},"intvolume":"        47","date_created":"2019-02-13T12:59:33Z","department":[{"_id":"VlKo"}],"citation":{"ama":"Kolmogorov V. Commutativity in the algorithmic Lovász local lemma. <i>SIAM Journal on Computing</i>. 2018;47(6):2029-2056. doi:<a href=\"https://doi.org/10.1137/16m1093306\">10.1137/16m1093306</a>","apa":"Kolmogorov, V. (2018). Commutativity in the algorithmic Lovász local lemma. <i>SIAM Journal on Computing</i>. Society for Industrial and Applied Mathematics. <a href=\"https://doi.org/10.1137/16m1093306\">https://doi.org/10.1137/16m1093306</a>","ieee":"V. Kolmogorov, “Commutativity in the algorithmic Lovász local lemma,” <i>SIAM Journal on Computing</i>, vol. 47, no. 6. Society for Industrial and Applied Mathematics, pp. 2029–2056, 2018.","ista":"Kolmogorov V. 2018. Commutativity in the algorithmic Lovász local lemma. SIAM Journal on Computing. 47(6), 2029–2056.","mla":"Kolmogorov, Vladimir. “Commutativity in the Algorithmic Lovász Local Lemma.” <i>SIAM Journal on Computing</i>, vol. 47, no. 6, Society for Industrial and Applied Mathematics, 2018, pp. 2029–56, doi:<a href=\"https://doi.org/10.1137/16m1093306\">10.1137/16m1093306</a>.","short":"V. Kolmogorov, SIAM Journal on Computing 47 (2018) 2029–2056.","chicago":"Kolmogorov, Vladimir. “Commutativity in the Algorithmic Lovász Local Lemma.” <i>SIAM Journal on Computing</i>. Society for Industrial and Applied Mathematics, 2018. <a href=\"https://doi.org/10.1137/16m1093306\">https://doi.org/10.1137/16m1093306</a>."},"publisher":"Society for Industrial and Applied Mathematics","month":"11","status":"public","page":"2029-2056","oa":1,"day":"08","year":"2018","volume":47,"title":"Commutativity in the algorithmic Lovász local lemma","language":[{"iso":"eng"}],"abstract":[{"lang":"eng","text":"We consider the recent formulation of the algorithmic Lov ́asz Local Lemma  [N. Har-vey and J. Vondr ́ak, inProceedings of FOCS, 2015, pp. 1327–1345; D. Achlioptas and F. Iliopoulos,inProceedings of SODA, 2016, pp. 2024–2038; D. Achlioptas, F. Iliopoulos, and V. Kolmogorov,ALocal Lemma for Focused Stochastic Algorithms, arXiv preprint, 2018] for finding objects that avoid“bad  features,”  or  “flaws.”   It  extends  the  Moser–Tardos  resampling  algorithm  [R.  A.  Moser  andG. Tardos,J. ACM, 57 (2010), 11] to more general discrete spaces.  At each step the method picks aflaw present in the current state and goes to a new state according to some prespecified probabilitydistribution (which depends on the current state and the selected flaw).  However, the recent formu-lation is less flexible than the Moser–Tardos method since it requires a specific flaw selection rule,whereas the algorithm of Moser and Tardos allows an arbitrary rule (and thus can potentially beimplemented more efficiently).  We formulate a new “commutativity” condition and prove that it issufficient for an arbitrary rule to work.  It also enables an efficient parallelization under an additionalassumption.  We then show that existing resampling oracles for perfect matchings and permutationsdo satisfy this condition."}],"main_file_link":[{"url":"https://arxiv.org/abs/1506.08547","open_access":"1"}],"ec_funded":1,"doi":"10.1137/16m1093306","publication_status":"published","type":"journal_article","publication":"SIAM Journal on Computing","date_updated":"2025-09-22T09:44:20Z","scopus_import":"1","article_processing_charge":"No"},{"oa_version":"Preprint","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"last_name":"Henzinger","first_name":"Monika H","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"last_name":"Krinninger","first_name":"Sebastian","full_name":"Krinninger, Sebastian"},{"full_name":"Nanongkai, Danupon","last_name":"Nanongkai","first_name":"Danupon"}],"external_id":{"arxiv":["1308.0776"]},"arxiv":1,"page":"947-1006","status":"public","month":"05","publisher":"Society for Industrial & Applied Mathematics","citation":{"ama":"Henzinger M, Krinninger S, Nanongkai D. Dynamic approximate all-pairs shortest paths: Breaking the O(mn) barrier and derandomization. <i>SIAM Journal on Computing</i>. 2016;45(3):947-1006. doi:<a href=\"https://doi.org/10.1137/140957299\">10.1137/140957299</a>","ieee":"M. Henzinger, S. Krinninger, and D. Nanongkai, “Dynamic approximate all-pairs shortest paths: Breaking the O(mn) barrier and derandomization,” <i>SIAM Journal on Computing</i>, vol. 45, no. 3. Society for Industrial &#38; Applied Mathematics, pp. 947–1006, 2016.","apa":"Henzinger, M., Krinninger, S., &#38; Nanongkai, D. (2016). Dynamic approximate all-pairs shortest paths: Breaking the O(mn) barrier and derandomization. <i>SIAM Journal on Computing</i>. Society for Industrial &#38; Applied Mathematics. <a href=\"https://doi.org/10.1137/140957299\">https://doi.org/10.1137/140957299</a>","chicago":"Henzinger, Monika, Sebastian Krinninger, and Danupon Nanongkai. “Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(Mn) Barrier and Derandomization.” <i>SIAM Journal on Computing</i>. Society for Industrial &#38; Applied Mathematics, 2016. <a href=\"https://doi.org/10.1137/140957299\">https://doi.org/10.1137/140957299</a>.","ista":"Henzinger M, Krinninger S, Nanongkai D. 2016. Dynamic approximate all-pairs shortest paths: Breaking the O(mn) barrier and derandomization. SIAM Journal on Computing. 45(3), 947–1006.","short":"M. Henzinger, S. Krinninger, D. Nanongkai, SIAM Journal on Computing 45 (2016) 947–1006.","mla":"Henzinger, Monika, et al. “Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(Mn) Barrier and Derandomization.” <i>SIAM Journal on Computing</i>, vol. 45, no. 3, Society for Industrial &#38; Applied Mathematics, 2016, pp. 947–1006, doi:<a href=\"https://doi.org/10.1137/140957299\">10.1137/140957299</a>."},"date_created":"2022-08-17T08:37:00Z","publication_identifier":{"issn":["0097-5397"],"eissn":["1095-7111"]},"intvolume":"        45","issue":"3","_id":"11891","date_published":"2016-05-01T00:00:00Z","quality_controlled":"1","publication_status":"published","doi":"10.1137/140957299","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1308.0776"}],"abstract":[{"text":"We study dynamic (1+𝜖)-approximation algorithms for the all-pairs shortest paths problem in unweighted undirected 𝑛-node 𝑚-edge graphs under edge deletions. The fastest algorithm for this problem is a randomized algorithm with a total update time of 𝑂̃ (𝑚𝑛/𝜖) and constant query time by Roditty and Zwick [SIAM J. Comput., 41 (2012), pp. 670--683]. The fastest deterministic algorithm is from a 1981 paper by Even and Shiloach [J. ACM, 28 (1981), pp. 1--4]; it has a total update time of 𝑂(𝑚𝑛2) and constant query time. We improve these results as follows: (1) We present an algorithm with a total update time of 𝑂̃ (𝑛5/2/𝜖) and constant query time that has an additive error of 2 in addition to the 1+𝜖 multiplicative error. This beats the previous 𝑂̃ (𝑚𝑛/𝜖) time when 𝑚=Ω(𝑛3/2). Note that the additive error is unavoidable since, even in the static case, an 𝑂(𝑛3−𝛿)-time (a so-called truly subcubic) combinatorial algorithm with 1+𝜖 multiplicative error cannot have an additive error less than 2−𝜖, unless we make a major breakthrough for Boolean matrix multiplication [D. Dor, S. Halrepin, and U. Zwick, SIAM J. Comput., 29 (2000), pp. 1740--1759] and many other long-standing problems [V. Vassilevska Williams and R. Williams, Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, 2010, pp. 645--654]. The algorithm can also be turned into a (2+𝜖)-approximation algorithm (without an additive error) with the same time guarantees, improving the recent (3+𝜖)-approximation algorithm with 𝑂̃ (𝑛5/2+𝑂(log(1/𝜖)/log𝑛√)) running time of Bernstein and Roditty [Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011, pp. 1355--1365] in terms of both approximation and time guarantees. (2) We present a deterministic algorithm with a total update time of 𝑂̃ (𝑚𝑛/𝜖) and a query time of 𝑂(loglog𝑛). The algorithm has a multiplicative error of 1+𝜖 and gives the first improved deterministic algorithm since 1981. It also answers an open question raised by Bernstein in [Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, 2013, pp. 725--734]. The deterministic algorithm can be turned into a deterministic fully dynamic (1+𝜖)-approximation with an amortized update time of 𝑂̃ (𝑚𝑛/(𝜖𝑡)) and a query time of 𝑂̃ (𝑡) for every 𝑡≤𝑛√. In order to achieve our results, we introduce two new techniques: (i) A monotone Even--Shiloach tree algorithm which maintains a bounded-distance shortest-paths tree on a certain type of emulator called a locally persevering emulator. (ii) A derandomization technique based on moving Even--Shiloach trees as a way to derandomize the standard random set argument. These techniques might be of independent interest.","lang":"eng"}],"language":[{"iso":"eng"}],"volume":45,"title":"Dynamic approximate all-pairs shortest paths: Breaking the O(mn) barrier and derandomization","year":"2016","day":"01","extern":"1","oa":1,"article_type":"original","article_processing_charge":"No","scopus_import":"1","date_updated":"2024-11-06T12:23:06Z","type":"journal_article","publication":"SIAM Journal on Computing"},{"day":"01","extern":"1","volume":31,"title":"Maintaining minimum spanning forests in dynamic graphs","year":"2001","language":[{"iso":"eng"}],"abstract":[{"text":"We present the first fully dynamic algorithm for maintaining a minimum spanning forest in time 𝑜(𝑛√) per operation. To be precise, the algorithm uses O(n1/3 log n) amortized time per update operation. The algorithm is fairly simple and deterministic. An immediate consequence is the first fully dynamic deterministic algorithm for maintaining connectivity and bipartiteness in amortized time O(n1/3 log n) per update, with O(1) worst case time per query.","lang":"eng"}],"author":[{"last_name":"Henzinger","first_name":"Monika H","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"full_name":"King, Valerie","first_name":"Valerie","last_name":"King"}],"oa_version":"None","doi":"10.1137/s0097539797327209","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_status":"published","date_updated":"2024-11-06T12:23:16Z","quality_controlled":"1","publication":"SIAM Journal on Computing","type":"journal_article","date_published":"2001-03-01T00:00:00Z","issue":"2","intvolume":"        31","publication_identifier":{"eissn":["1095-7111"],"issn":["0097-5397"]},"_id":"11892","scopus_import":"1","date_created":"2022-08-17T08:43:43Z","citation":{"ista":"Henzinger M, King V. 2001. Maintaining minimum spanning forests in dynamic graphs. SIAM Journal on Computing. 31(2), 364–374.","short":"M. Henzinger, V. King, SIAM Journal on Computing 31 (2001) 364–374.","mla":"Henzinger, Monika, and Valerie King. “Maintaining Minimum Spanning Forests in Dynamic Graphs.” <i>SIAM Journal on Computing</i>, vol. 31, no. 2, Society for Industrial &#38; Applied Mathematics, 2001, pp. 364–74, doi:<a href=\"https://doi.org/10.1137/s0097539797327209\">10.1137/s0097539797327209</a>.","chicago":"Henzinger, Monika, and Valerie King. “Maintaining Minimum Spanning Forests in Dynamic Graphs.” <i>SIAM Journal on Computing</i>. Society for Industrial &#38; Applied Mathematics, 2001. <a href=\"https://doi.org/10.1137/s0097539797327209\">https://doi.org/10.1137/s0097539797327209</a>.","ieee":"M. Henzinger and V. King, “Maintaining minimum spanning forests in dynamic graphs,” <i>SIAM Journal on Computing</i>, vol. 31, no. 2. Society for Industrial &#38; Applied Mathematics, pp. 364–374, 2001.","ama":"Henzinger M, King V. Maintaining minimum spanning forests in dynamic graphs. <i>SIAM Journal on Computing</i>. 2001;31(2):364-374. doi:<a href=\"https://doi.org/10.1137/s0097539797327209\">10.1137/s0097539797327209</a>","apa":"Henzinger, M., &#38; King, V. (2001). Maintaining minimum spanning forests in dynamic graphs. <i>SIAM Journal on Computing</i>. Society for Industrial &#38; Applied Mathematics. <a href=\"https://doi.org/10.1137/s0097539797327209\">https://doi.org/10.1137/s0097539797327209</a>"},"publisher":"Society for Industrial & Applied Mathematics","status":"public","article_processing_charge":"No","month":"03","page":"364-374","article_type":"original"},{"keyword":["directed graph","exploration algorithm"],"acknowledgement":"We thank Prabhakar Raghavan for bringing to our attention the literature on the s-t connectivity  problem. We also thank  an anonymous referee for many helpful comments which improved the presentation of the paper.","oa_version":"None","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"last_name":"Albers","first_name":"Susanne","full_name":"Albers, Susanne"},{"last_name":"Henzinger","first_name":"Monika H","full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530"}],"publication_identifier":{"eissn":["1095-7111"],"issn":["0097-5397"]},"intvolume":"        29","issue":"4","_id":"11694","quality_controlled":"1","date_published":"2000-07-01T00:00:00Z","status":"public","month":"07","page":"1164-1188","date_created":"2022-07-29T09:04:36Z","publisher":"Society for Industrial and Applied Mathematics","citation":{"chicago":"Albers, Susanne, and Monika Henzinger. “Exploring Unknown Environments.” <i>SIAM Journal on Computing</i>. Society for Industrial and Applied Mathematics, 2000. <a href=\"https://doi.org/10.1137/s009753979732428x\">https://doi.org/10.1137/s009753979732428x</a>.","ista":"Albers S, Henzinger M. 2000. Exploring unknown environments. SIAM Journal on Computing. 29(4), 1164–1188.","mla":"Albers, Susanne, and Monika Henzinger. “Exploring Unknown Environments.” <i>SIAM Journal on Computing</i>, vol. 29, no. 4, Society for Industrial and Applied Mathematics, 2000, pp. 1164–88, doi:<a href=\"https://doi.org/10.1137/s009753979732428x\">10.1137/s009753979732428x</a>.","short":"S. Albers, M. Henzinger, SIAM Journal on Computing 29 (2000) 1164–1188.","apa":"Albers, S., &#38; Henzinger, M. (2000). Exploring unknown environments. <i>SIAM Journal on Computing</i>. El Paso, TX, United States: Society for Industrial and Applied Mathematics. <a href=\"https://doi.org/10.1137/s009753979732428x\">https://doi.org/10.1137/s009753979732428x</a>","ama":"Albers S, Henzinger M. Exploring unknown environments. <i>SIAM Journal on Computing</i>. 2000;29(4):1164-1188. doi:<a href=\"https://doi.org/10.1137/s009753979732428x\">10.1137/s009753979732428x</a>","ieee":"S. Albers and M. Henzinger, “Exploring unknown environments,” <i>SIAM Journal on Computing</i>, vol. 29, no. 4. Society for Industrial and Applied Mathematics, pp. 1164–1188, 2000."},"language":[{"iso":"eng"}],"abstract":[{"lang":"eng","text":"We consider exploration problems where a robot has to construct a complete map of an unknown environment. We assume that the environment is modeled by a directed, strongly connected graph. The robot's task is to visit all nodes and edges of the graph using the minimum number R of edge traversals. Deng and Papadimitriou [Proceedings of the 31st Symposium on the Foundations of Computer Science, 1990, pp. 356-361] showed an upper bound for R ofd O(d)m and Koutsoupias (reported by Deng and Papadimitriou) gave a lower bound of Ω≠(d2m), where m is the number of edges in the graph and d is the minimum number of edges that have to be added to make the graph Eulerian.  We give the 1rst subexponential algorithm for this exploration problem, which achieves an upper bound of dO(logd)m.  We also show a matching lower bound of d≠(logd)m for our algorithm. Additionally, we give lower bounds of 2≠(d)m, respectively, d≠(logd)m for various other natural exploration algorithms."}],"day":"01","conference":{"end_date":"1997-05-06","name":"STOC97: 29th Annual Symposium on Theory of Computing","location":"El Paso, TX, United States","start_date":"1997-05-04"},"extern":"1","title":"Exploring unknown environments","volume":29,"year":"2000","doi":"10.1137/s009753979732428x","publication_status":"published","scopus_import":"1","date_updated":"2024-11-06T12:09:07Z","type":"journal_article","publication":"SIAM Journal on Computing","article_processing_charge":"No","article_type":"original"},{"scopus_import":"1","_id":"11893","publication_identifier":{"issn":["0097-5397"],"eissn":["1095-7111"]},"intvolume":"        29","issue":"6","date_published":"2000-11-01T00:00:00Z","type":"journal_article","publication":"SIAM Journal on Computing","quality_controlled":"1","date_updated":"2024-11-06T12:00:56Z","article_type":"original","page":"1761-1815","article_processing_charge":"No","month":"11","status":"public","citation":{"apa":"Henzinger, M. (2000). Improved data structures for fully dynamic biconnectivity. <i>SIAM Journal on Computing</i>. Society for Industrial &#38; Applied Mathematics. <a href=\"https://doi.org/10.1137/s0097539794263907\">https://doi.org/10.1137/s0097539794263907</a>","ama":"Henzinger M. Improved data structures for fully dynamic biconnectivity. <i>SIAM Journal on Computing</i>. 2000;29(6):1761-1815. doi:<a href=\"https://doi.org/10.1137/s0097539794263907\">10.1137/s0097539794263907</a>","ieee":"M. Henzinger, “Improved data structures for fully dynamic biconnectivity,” <i>SIAM Journal on Computing</i>, vol. 29, no. 6. Society for Industrial &#38; Applied Mathematics, pp. 1761–1815, 2000.","chicago":"Henzinger, Monika. “Improved Data Structures for Fully Dynamic Biconnectivity.” <i>SIAM Journal on Computing</i>. Society for Industrial &#38; Applied Mathematics, 2000. <a href=\"https://doi.org/10.1137/s0097539794263907\">https://doi.org/10.1137/s0097539794263907</a>.","mla":"Henzinger, Monika. “Improved Data Structures for Fully Dynamic Biconnectivity.” <i>SIAM Journal on Computing</i>, vol. 29, no. 6, Society for Industrial &#38; Applied Mathematics, 2000, pp. 1761–815, doi:<a href=\"https://doi.org/10.1137/s0097539794263907\">10.1137/s0097539794263907</a>.","short":"M. Henzinger, SIAM Journal on Computing 29 (2000) 1761–1815.","ista":"Henzinger M. 2000. Improved data structures for fully dynamic biconnectivity. SIAM Journal on Computing. 29(6), 1761–1815."},"publisher":"Society for Industrial & Applied Mathematics","date_created":"2022-08-17T08:45:41Z","abstract":[{"text":"We present fully dynamic algorithms for maintaining the biconnected components in general and plane graphs.\r\n\r\nA fully dynamic algorithm maintains a graph during a sequence of insertions and deletions of edges or isolated vertices. Let m be the number of edges and n be the number of vertices in a graph. The time per operation of the best deterministic algorithms is 𝑂(𝑛√) in general graphs and O(log n) in plane graphs for fully dynamic connectivity and O(min m2/3 ,n}) in general graphs and 𝑂(𝑛√) in plane graphs for fully dynamic biconnectivity. We improve the later running times to 𝑂(𝑚log𝑛‾‾‾‾‾‾‾√) in general graphs and O(log 2n ) in plane graphs. Our algorithm for general graphscan also find the biconnected components of all vertices in time O(n).","lang":"eng"}],"language":[{"iso":"eng"}],"year":"2000","title":"Improved data structures for fully dynamic biconnectivity","volume":29,"extern":"1","day":"01","publication_status":"published","doi":"10.1137/s0097539794263907","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"None","author":[{"first_name":"Monika H","last_name":"Henzinger","orcid":"0000-0002-5008-6530","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H"}]},{"article_processing_charge":"No","article_type":"original","scopus_import":"1","type":"journal_article","publication":"SIAM Journal on Computing","date_updated":"2022-06-03T06:41:56Z","doi":"10.1137/S0097539790179919 ","publication_status":"published","main_file_link":[{"url":"https://epubs.siam.org/doi/10.1137/S0097539790179919"}],"publist_id":"2092","language":[{"iso":"eng"}],"abstract":[{"text":"A collection of geometric selection lemmas is proved, such as the following: For any set P of n points in three-dimensional space and any set S of m spheres, where each sphere passes through a distinct point pair in P. there exists a point x, not necessarily in P, that is enclosed by Ω(m2/(n2 log6 n2/m)) of the spheres in S. Similar results apply in arbitrary fixed dimensions, and for geometric bodies other than spheres. The results have applications in reducing the size of geometric structures, such as three-dimensional Delaunay triangulations and Gabriel graphs, by adding extra points to their defining sets.","lang":"eng"}],"extern":"1","day":"01","year":"1994","title":"Selecting heavily covered points","volume":23,"month":"12","status":"public","page":"1138 - 1151","date_created":"2018-12-11T12:06:33Z","publisher":"SIAM","citation":{"ama":"Chazelle B, Edelsbrunner H, Guibas L, Hershberger J, Seidel R, Sharir M. Selecting heavily covered points. <i>SIAM Journal on Computing</i>. 1994;23(6):1138-1151. doi:<a href=\"https://doi.org/10.1137/S0097539790179919 \">10.1137/S0097539790179919 </a>","apa":"Chazelle, B., Edelsbrunner, H., Guibas, L., Hershberger, J., Seidel, R., &#38; Sharir, M. (1994). Selecting heavily covered points. <i>SIAM Journal on Computing</i>. SIAM. <a href=\"https://doi.org/10.1137/S0097539790179919 \">https://doi.org/10.1137/S0097539790179919 </a>","ieee":"B. Chazelle, H. Edelsbrunner, L. Guibas, J. Hershberger, R. Seidel, and M. Sharir, “Selecting heavily covered points,” <i>SIAM Journal on Computing</i>, vol. 23, no. 6. SIAM, pp. 1138–1151, 1994.","chicago":"Chazelle, Bernard, Herbert Edelsbrunner, Leonidas Guibas, John Hershberger, Raimund Seidel, and Micha Sharir. “Selecting Heavily Covered Points.” <i>SIAM Journal on Computing</i>. SIAM, 1994. <a href=\"https://doi.org/10.1137/S0097539790179919 \">https://doi.org/10.1137/S0097539790179919 </a>.","mla":"Chazelle, Bernard, et al. “Selecting Heavily Covered Points.” <i>SIAM Journal on Computing</i>, vol. 23, no. 6, SIAM, 1994, pp. 1138–51, doi:<a href=\"https://doi.org/10.1137/S0097539790179919 \">10.1137/S0097539790179919 </a>.","short":"B. Chazelle, H. Edelsbrunner, L. Guibas, J. Hershberger, R. Seidel, M. Sharir, SIAM Journal on Computing 23 (1994) 1138–1151.","ista":"Chazelle B, Edelsbrunner H, Guibas L, Hershberger J, Seidel R, Sharir M. 1994. Selecting heavily covered points. SIAM Journal on Computing. 23(6), 1138–1151."},"_id":"4033","intvolume":"        23","issue":"6","publication_identifier":{"issn":["0097-5397"]},"quality_controlled":"1","date_published":"1994-12-01T00:00:00Z","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","oa_version":"None","author":[{"full_name":"Chazelle, Bernard","first_name":"Bernard","last_name":"Chazelle"},{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833","first_name":"Herbert","last_name":"Edelsbrunner"},{"full_name":"Guibas, Leonidas","first_name":"Leonidas","last_name":"Guibas"},{"first_name":"John","last_name":"Hershberger","full_name":"Hershberger, John"},{"last_name":"Seidel","first_name":"Raimund","full_name":"Seidel, Raimund"},{"full_name":"Sharir, Micha","last_name":"Sharir","first_name":"Micha"}]},{"date_updated":"2022-03-30T08:07:21Z","type":"journal_article","publication":"SIAM Journal on Computing","scopus_import":"1","article_processing_charge":"No","article_type":"original","day":"01","extern":"1","title":"Computing a face in an arrangement of line segments and related problems","volume":22,"year":"1993","language":[{"iso":"eng"}],"publist_id":"2087","abstract":[{"lang":"eng","text":"This paper presents a randomized incremental algorithm for computing a single face in an arrangement of n line segments in the plane that is fairly simple to implement. The expected running time of the algorithm is O(nα(n)log n). The analysis of the algorithm uses a novel approach that generalizes and extends the Clarkson-Shor analysis technique [in Discrete Comput. Geom., 4(1989), pp. 387-421]. A few extensions of the technique, obtaining efficient randomized incremental algorithms for constructing the entire arrangement of a collection of line segments and for computing a single face in an arrangement of Jordan arcs are also presented."}],"main_file_link":[{"url":"https://epubs.siam.org/doi/10.1137/0222077"}],"doi":"10.1137/0222077 ","publication_status":"published","quality_controlled":"1","date_published":"1993-12-01T00:00:00Z","issue":"6","intvolume":"        22","publication_identifier":{"issn":["0097-5397"]},"_id":"4036","date_created":"2018-12-11T12:06:34Z","publisher":"SIAM","citation":{"chicago":"Chazelle, Bernard, Herbert Edelsbrunner, Leonidas Guibas, Micha Sharir, and Jack Snoeyink. “Computing a Face in an Arrangement of Line Segments and Related Problems.” <i>SIAM Journal on Computing</i>. SIAM, 1993. <a href=\"https://doi.org/10.1137/0222077 \">https://doi.org/10.1137/0222077 </a>.","mla":"Chazelle, Bernard, et al. “Computing a Face in an Arrangement of Line Segments and Related Problems.” <i>SIAM Journal on Computing</i>, vol. 22, no. 6, SIAM, 1993, pp. 1286–302, doi:<a href=\"https://doi.org/10.1137/0222077 \">10.1137/0222077 </a>.","short":"B. Chazelle, H. Edelsbrunner, L. Guibas, M. Sharir, J. Snoeyink, SIAM Journal on Computing 22 (1993) 1286–1302.","ista":"Chazelle B, Edelsbrunner H, Guibas L, Sharir M, Snoeyink J. 1993. Computing a face in an arrangement of line segments and related problems. SIAM Journal on Computing. 22(6), 1286–1302.","apa":"Chazelle, B., Edelsbrunner, H., Guibas, L., Sharir, M., &#38; Snoeyink, J. (1993). Computing a face in an arrangement of line segments and related problems. <i>SIAM Journal on Computing</i>. SIAM. <a href=\"https://doi.org/10.1137/0222077 \">https://doi.org/10.1137/0222077 </a>","ieee":"B. Chazelle, H. Edelsbrunner, L. Guibas, M. Sharir, and J. Snoeyink, “Computing a face in an arrangement of line segments and related problems,” <i>SIAM Journal on Computing</i>, vol. 22, no. 6. SIAM, pp. 1286–1302, 1993.","ama":"Chazelle B, Edelsbrunner H, Guibas L, Sharir M, Snoeyink J. Computing a face in an arrangement of line segments and related problems. <i>SIAM Journal on Computing</i>. 1993;22(6):1286-1302. doi:<a href=\"https://doi.org/10.1137/0222077 \">10.1137/0222077 </a>"},"status":"public","month":"12","page":"1286 - 1302","acknowledgement":"The authors wish to express their gratitude for the generous support and hospitality of the DEC Palo Alto Systems Research Center.","author":[{"first_name":"Bernard","last_name":"Chazelle","full_name":"Chazelle, Bernard"},{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833","full_name":"Edelsbrunner, Herbert","last_name":"Edelsbrunner","first_name":"Herbert"},{"first_name":"Leonidas","last_name":"Guibas","full_name":"Guibas, Leonidas"},{"last_name":"Sharir","first_name":"Micha","full_name":"Sharir, Micha"},{"full_name":"Snoeyink, Jack","last_name":"Snoeyink","first_name":"Jack"}],"oa_version":"None","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17"},{"extern":"1","day":"01","year":"1993","title":"On the zone theorem for hyperplane arrangements","volume":22,"publist_id":"2085","language":[{"iso":"eng"}],"abstract":[{"text":"The zone theorem for an arrangement of n hyperplanes in d-dimensional real space says that the total number of faces bounding the cells intersected by another hyperplane is O(n(d-1)). This result is the basis of a time-optimal incremental algorithm that constructs a hyperplane arrangement and has a host of other algorithmic and combinatorial applications. Unfortunately, the original proof of the zone theorem, for d greater-than-or-equal-to 3, turned out to contain a serious and irreparable error. This paper presents a new proof of the theorem. The proof is based on an inductive argument, which also applies in the case of pseudohyperplane arrangements. The fallacies of the old proof along with some ways of partially saving that approach are briefly discussed.","lang":"eng"}],"main_file_link":[{"url":"https://epubs.siam.org/doi/10.1137/0222031"}],"doi":"10.1137/0222031","publication_status":"published","type":"journal_article","publication":"SIAM Journal on Computing","date_updated":"2022-03-29T13:25:02Z","scopus_import":"1","article_processing_charge":"No","article_type":"original","acknowledgement":"National Science Foundation under grant CCR-89- 21421.","author":[{"full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","last_name":"Edelsbrunner","first_name":"Herbert"},{"full_name":"Seidel, Raimund","last_name":"Seidel","first_name":"Raimund"},{"full_name":"Sharir, Micha","last_name":"Sharir","first_name":"Micha"}],"user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","oa_version":"None","quality_controlled":"1","date_published":"1993-04-01T00:00:00Z","_id":"4041","issue":"2","publication_identifier":{"issn":["0097-5397"]},"intvolume":"        22","date_created":"2018-12-11T12:06:35Z","citation":{"chicago":"Edelsbrunner, Herbert, Raimund Seidel, and Micha Sharir. “On the Zone Theorem for Hyperplane Arrangements.” <i>SIAM Journal on Computing</i>. SIAM, 1993. <a href=\"https://doi.org/10.1137/0222031\">https://doi.org/10.1137/0222031</a>.","ista":"Edelsbrunner H, Seidel R, Sharir M. 1993. On the zone theorem for hyperplane arrangements. SIAM Journal on Computing. 22(2), 418–429.","short":"H. Edelsbrunner, R. Seidel, M. Sharir, SIAM Journal on Computing 22 (1993) 418–429.","mla":"Edelsbrunner, Herbert, et al. “On the Zone Theorem for Hyperplane Arrangements.” <i>SIAM Journal on Computing</i>, vol. 22, no. 2, SIAM, 1993, pp. 418–29, doi:<a href=\"https://doi.org/10.1137/0222031\">10.1137/0222031</a>.","ama":"Edelsbrunner H, Seidel R, Sharir M. On the zone theorem for hyperplane arrangements. <i>SIAM Journal on Computing</i>. 1993;22(2):418-429. doi:<a href=\"https://doi.org/10.1137/0222031\">10.1137/0222031</a>","ieee":"H. Edelsbrunner, R. Seidel, and M. Sharir, “On the zone theorem for hyperplane arrangements,” <i>SIAM Journal on Computing</i>, vol. 22, no. 2. SIAM, pp. 418–429, 1993.","apa":"Edelsbrunner, H., Seidel, R., &#38; Sharir, M. (1993). On the zone theorem for hyperplane arrangements. <i>SIAM Journal on Computing</i>. SIAM. <a href=\"https://doi.org/10.1137/0222031\">https://doi.org/10.1137/0222031</a>"},"publisher":"SIAM","month":"04","status":"public","page":"418 - 429"},{"scopus_import":"1","date_updated":"2022-03-30T07:43:13Z","type":"journal_article","publication":"SIAM Journal on Computing","article_processing_charge":"No","article_type":"original","language":[{"iso":"eng"}],"publist_id":"2086","abstract":[{"lang":"eng","text":"It is shown that a triangulation of a set of n points in the plane that minimizes the maximum edge length can be computed in time 0(n2). The algorithm is reasonably easy to implement and is based on the theorem that there is a triangulation with minmax edge length that contains the relative neighborhood graph of the points as a subgraph. With minor modifications the algorithm works for arbitrary normed metrics."}],"day":"01","extern":"1","volume":22,"title":"A quadratic time algorithm for the minmax length triangulation","year":"1993","doi":"10.1137/0222036 ","publication_status":"published","main_file_link":[{"url":"https://epubs.siam.org/doi/10.1137/0222036"}],"issue":"3","intvolume":"        22","publication_identifier":{"issn":["0097-5397"]},"_id":"4042","quality_controlled":"1","date_published":"1993-06-01T00:00:00Z","status":"public","month":"06","page":"527 - 551","date_created":"2018-12-11T12:06:36Z","citation":{"chicago":"Edelsbrunner, Herbert, and Tiow Tan. “A Quadratic Time Algorithm for the Minmax Length Triangulation.” <i>SIAM Journal on Computing</i>. SIAM, 1993. <a href=\"https://doi.org/10.1137/0222036 \">https://doi.org/10.1137/0222036 </a>.","mla":"Edelsbrunner, Herbert, and Tiow Tan. “A Quadratic Time Algorithm for the Minmax Length Triangulation.” <i>SIAM Journal on Computing</i>, vol. 22, no. 3, SIAM, 1993, pp. 527–51, doi:<a href=\"https://doi.org/10.1137/0222036 \">10.1137/0222036 </a>.","short":"H. Edelsbrunner, T. Tan, SIAM Journal on Computing 22 (1993) 527–551.","ista":"Edelsbrunner H, Tan T. 1993. A quadratic time algorithm for the minmax length triangulation. SIAM Journal on Computing. 22(3), 527–551.","apa":"Edelsbrunner, H., &#38; Tan, T. (1993). A quadratic time algorithm for the minmax length triangulation. <i>SIAM Journal on Computing</i>. SIAM. <a href=\"https://doi.org/10.1137/0222036 \">https://doi.org/10.1137/0222036 </a>","ieee":"H. Edelsbrunner and T. Tan, “A quadratic time algorithm for the minmax length triangulation,” <i>SIAM Journal on Computing</i>, vol. 22, no. 3. SIAM, pp. 527–551, 1993.","ama":"Edelsbrunner H, Tan T. A quadratic time algorithm for the minmax length triangulation. <i>SIAM Journal on Computing</i>. 1993;22(3):527-551. doi:<a href=\"https://doi.org/10.1137/0222036 \">10.1137/0222036 </a>"},"publisher":"SIAM","acknowledgement":"The authors thank an anonymous referee for suggestions on the organization of this paper.","oa_version":"None","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","author":[{"orcid":"0000-0002-9823-6833","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","full_name":"Edelsbrunner, Herbert","last_name":"Edelsbrunner","first_name":"Herbert"},{"last_name":"Tan","first_name":"Tiow","full_name":"Tan, Tiow"}]},{"main_file_link":[{"url":"https://epubs.siam.org/doi/10.1137/0913058"}],"publication_status":"published","doi":"10.1137/0913058","year":"1992","title":"An O(n^2 log n) time algorithm for the MinMax angle triangulation","volume":13,"extern":"1","day":"01","abstract":[{"text":"It is shown that a triangulation of a set of n points in the plane that minimizes the maximum angle can be computed in time O(n2 log n) and space O(n). The algorithm is fairly easy to implement and is based on the edge-insertion scheme that iteratively improves an arbitrary initial triangulation. It can be extended to the case where edges are prescribed, and, within the same time- and space-bounds, it can lexicographically minimize the sorted angle vector if the point set is in general position. Experimental results on the efficiency of the algorithm and the quality of the triangulations obtained are included.","lang":"eng"}],"publist_id":"2081","language":[{"iso":"eng"}],"article_type":"original","article_processing_charge":"No","publication":"SIAM Journal on Scientific Computing","type":"journal_article","date_updated":"2022-03-16T09:35:05Z","author":[{"orcid":"0000-0002-9823-6833","full_name":"Edelsbrunner, Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","first_name":"Herbert","last_name":"Edelsbrunner"},{"last_name":"Tan","first_name":"Tiow","full_name":"Tan, Tiow"},{"full_name":"Waupotitsch, Roman","first_name":"Roman","last_name":"Waupotitsch"}],"user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","oa_version":"None","publisher":"Society for Industrial and Applied Mathematics ","citation":{"chicago":"Edelsbrunner, Herbert, Tiow Tan, and Roman Waupotitsch. “An O(N^2 Log n) Time Algorithm for the MinMax Angle Triangulation.” <i>SIAM Journal on Scientific Computing</i>. Society for Industrial and Applied Mathematics , 1992. <a href=\"https://doi.org/10.1137/0913058\">https://doi.org/10.1137/0913058</a>.","mla":"Edelsbrunner, Herbert, et al. “An O(N^2 Log n) Time Algorithm for the MinMax Angle Triangulation.” <i>SIAM Journal on Scientific Computing</i>, vol. 13, no. 4, Society for Industrial and Applied Mathematics , 1992, pp. 994–1008, doi:<a href=\"https://doi.org/10.1137/0913058\">10.1137/0913058</a>.","short":"H. Edelsbrunner, T. Tan, R. Waupotitsch, SIAM Journal on Scientific Computing 13 (1992) 994–1008.","ista":"Edelsbrunner H, Tan T, Waupotitsch R. 1992. An O(n^2 log n) time algorithm for the MinMax angle triangulation. SIAM Journal on Scientific Computing. 13(4), 994–1008.","apa":"Edelsbrunner, H., Tan, T., &#38; Waupotitsch, R. (1992). An O(n^2 log n) time algorithm for the MinMax angle triangulation. <i>SIAM Journal on Scientific Computing</i>. Society for Industrial and Applied Mathematics . <a href=\"https://doi.org/10.1137/0913058\">https://doi.org/10.1137/0913058</a>","ieee":"H. Edelsbrunner, T. Tan, and R. Waupotitsch, “An O(n^2 log n) time algorithm for the MinMax angle triangulation,” <i>SIAM Journal on Scientific Computing</i>, vol. 13, no. 4. Society for Industrial and Applied Mathematics , pp. 994–1008, 1992.","ama":"Edelsbrunner H, Tan T, Waupotitsch R. An O(n^2 log n) time algorithm for the MinMax angle triangulation. <i>SIAM Journal on Scientific Computing</i>. 1992;13(4):994-1008. doi:<a href=\"https://doi.org/10.1137/0913058\">10.1137/0913058</a>"},"date_created":"2018-12-11T12:06:36Z","page":"994 - 1008","month":"07","status":"public","date_published":"1992-07-01T00:00:00Z","quality_controlled":"1","_id":"4043","issue":"4","publication_identifier":{"eissn":["1095-7111"],"issn":["0097-5397"]},"intvolume":"        13"}]