[{"external_id":{"isi":["001082972300004"],"arxiv":["1811.01421"]},"quality_controlled":"1","project":[{"_id":"268A44D6-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","name":"Elastic Coordination for Scalable Machine Learning","grant_number":"805223"}],"day":"25","volume":52,"oa_version":"Preprint","ec_funded":1,"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1811.01421"}],"abstract":[{"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.","lang":"eng"}],"article_type":"original","publication_status":"published","publisher":"Society for Industrial and Applied Mathematics","article_processing_charge":"No","publication_identifier":{"eissn":["1095-7111"],"issn":["0097-5397"]},"doi":"10.1137/20M1375851","date_published":"2023-07-25T00:00:00Z","year":"2023","citation":{"ama":"Alistarh D-A, Aspnes J, Ellen F, Gelashvili R, Zhu L. Why extension-based proofs fail. SIAM Journal on Computing. 2023;52(4):913-944. doi:10.1137/20M1375851","chicago":"Alistarh, Dan-Adrian, James Aspnes, Faith Ellen, Rati Gelashvili, and Leqi Zhu. “Why Extension-Based Proofs Fail.” SIAM Journal on Computing. Society for Industrial and Applied Mathematics, 2023. https://doi.org/10.1137/20M1375851.","short":"D.-A. Alistarh, J. Aspnes, F. Ellen, R. Gelashvili, L. Zhu, SIAM Journal on Computing 52 (2023) 913–944.","apa":"Alistarh, D.-A., Aspnes, J., Ellen, F., Gelashvili, R., & Zhu, L. (2023). Why extension-based proofs fail. SIAM Journal on Computing. Society for Industrial and Applied Mathematics. https://doi.org/10.1137/20M1375851","ieee":"D.-A. Alistarh, J. Aspnes, F. Ellen, R. Gelashvili, and L. Zhu, “Why extension-based proofs fail,” SIAM Journal on Computing, vol. 52, no. 4. Society for Industrial and Applied Mathematics, pp. 913–944, 2023.","mla":"Alistarh, Dan-Adrian, et al. “Why Extension-Based Proofs Fail.” SIAM Journal on Computing, vol. 52, no. 4, Society for Industrial and Applied Mathematics, 2023, pp. 913–44, doi:10.1137/20M1375851.","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."},"title":"Why extension-based proofs fail","isi":1,"date_updated":"2025-05-14T11:26:06Z","month":"07","department":[{"_id":"DaAl"}],"publication":"SIAM Journal on Computing","language":[{"iso":"eng"}],"scopus_import":"1","date_created":"2023-09-24T22:01:11Z","status":"public","page":"913-944","intvolume":" 52","_id":"14364","arxiv":1,"related_material":{"record":[{"status":"public","id":"6676","relation":"earlier_version"}]},"oa":1,"author":[{"first_name":"Dan-Adrian","orcid":"0000-0003-3650-940X","last_name":"Alistarh","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","full_name":"Alistarh, Dan-Adrian"},{"first_name":"James","last_name":"Aspnes","full_name":"Aspnes, James"},{"first_name":"Faith","last_name":"Ellen","full_name":"Ellen, Faith"},{"first_name":"Rati","full_name":"Gelashvili, Rati","last_name":"Gelashvili"},{"first_name":"Leqi","full_name":"Zhu, Leqi","id":"a2117c59-cee4-11ed-b9d0-874ecf0f8ac5","last_name":"Zhu"}],"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.","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"journal_article","issue":"4"},{"date_created":"2023-11-19T23:00:56Z","status":"public","scopus_import":"1","publication":"SIAM Journal on Computing","language":[{"iso":"eng"}],"intvolume":" 52","page":"1132-1192","_id":"14558","issue":"5","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","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","full_name":"Bhattacharya, Sayan","first_name":"Sayan"},{"first_name":"Monika H","orcid":"0000-0002-5008-6530","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H"},{"full_name":"Nanongkai, Danupon","last_name":"Nanongkai","first_name":"Danupon"},{"full_name":"Wu, Xiaowei","last_name":"Wu","first_name":"Xiaowei"}],"type":"journal_article","oa_version":"None","volume":52,"day":"01","ec_funded":1,"external_id":{"isi":["001116719500002"]},"quality_controlled":"1","project":[{"grant_number":"101019564","name":"The design and evaluation of modern fully dynamic data structures","_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","call_identifier":"H2020"},{"_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe","name":"Fast Algorithms for a Reactive Network Layer","grant_number":"P33775"},{"_id":"34def286-11ca-11ed-8bc3-da5948e1613c","name":"Efficient algorithms","grant_number":"Z00422"},{"grant_number":"I05982","name":"Static and Dynamic Hierarchical Graph Decompositions","_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103"}],"abstract":[{"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.","lang":"eng"}],"article_type":"original","date_published":"2023-10-01T00:00:00Z","year":"2023","citation":{"mla":"Bhattacharya, Sayan, et al. “Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover.” SIAM Journal on Computing, vol. 52, no. 5, Society for Industrial and Applied Mathematics, 2023, pp. 1132–92, doi:10.1137/21M1428649.","ieee":"S. Bhattacharya, M. Henzinger, D. Nanongkai, and X. Wu, “Deterministic near-optimal approximation algorithms for dynamic set cover,” SIAM Journal on Computing, vol. 52, no. 5. Society for Industrial and Applied Mathematics, pp. 1132–1192, 2023.","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.","chicago":"Bhattacharya, Sayan, Monika Henzinger, Danupon Nanongkai, and Xiaowei Wu. “Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover.” SIAM Journal on Computing. Society for Industrial and Applied Mathematics, 2023. https://doi.org/10.1137/21M1428649.","ama":"Bhattacharya S, Henzinger M, Nanongkai D, Wu X. Deterministic near-optimal approximation algorithms for dynamic set cover. SIAM Journal on Computing. 2023;52(5):1132-1192. doi:10.1137/21M1428649","apa":"Bhattacharya, S., Henzinger, M., Nanongkai, D., & Wu, X. (2023). Deterministic near-optimal approximation algorithms for dynamic set cover. SIAM Journal on Computing. Society for Industrial and Applied Mathematics. https://doi.org/10.1137/21M1428649","short":"S. Bhattacharya, M. Henzinger, D. Nanongkai, X. Wu, SIAM Journal on Computing 52 (2023) 1132–1192."},"publication_status":"published","publisher":"Society for Industrial and Applied Mathematics","publication_identifier":{"issn":["0097-5397"],"eissn":["1095-7111"]},"article_processing_charge":"No","doi":"10.1137/21M1428649","date_updated":"2025-09-09T13:19:49Z","month":"10","department":[{"_id":"MoHe"}],"title":"Deterministic near-optimal approximation algorithms for dynamic set cover","isi":1},{"issue":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","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. ","author":[{"full_name":"Krokhin, Andrei","last_name":"Krokhin","first_name":"Andrei"},{"first_name":"Jakub","orcid":"0000-0003-1245-3456","last_name":"Opršal","full_name":"Opršal, Jakub","id":"ec596741-c539-11ec-b829-c79322a91242"},{"full_name":"Wrochna, Marcin","last_name":"Wrochna","first_name":"Marcin"},{"full_name":"Živný, Stanislav","last_name":"Živný","first_name":"Stanislav"}],"type":"journal_article","oa":1,"_id":"12563","arxiv":1,"intvolume":" 52","page":"38-79","status":"public","date_created":"2023-02-16T07:03:52Z","keyword":["General Mathematics","General Computer Science"],"scopus_import":"1","publication":"SIAM Journal on Computing","language":[{"iso":"eng"}],"date_updated":"2025-05-14T10:51:32Z","month":"01","department":[{"_id":"UlWa"}],"title":"Topology and adjunction in promise constraint satisfaction","isi":1,"date_published":"2023-01-01T00:00:00Z","year":"2023","citation":{"ieee":"A. Krokhin, J. Opršal, M. Wrochna, and S. Živný, “Topology and adjunction in promise constraint satisfaction,” SIAM Journal on Computing, vol. 52, no. 1. Society for Industrial and Applied Mathematics, pp. 38–79, 2023.","mla":"Krokhin, Andrei, et al. “Topology and Adjunction in Promise Constraint Satisfaction.” SIAM Journal on Computing, vol. 52, no. 1, Society for Industrial and Applied Mathematics, 2023, pp. 38–79, doi:10.1137/20m1378223.","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.","ama":"Krokhin A, Opršal J, Wrochna M, Živný S. Topology and adjunction in promise constraint satisfaction. SIAM Journal on Computing. 2023;52(1):38-79. doi:10.1137/20m1378223","chicago":"Krokhin, Andrei, Jakub Opršal, Marcin Wrochna, and Stanislav Živný. “Topology and Adjunction in Promise Constraint Satisfaction.” SIAM Journal on Computing. Society for Industrial and Applied Mathematics, 2023. https://doi.org/10.1137/20m1378223.","short":"A. Krokhin, J. Opršal, M. Wrochna, S. Živný, SIAM Journal on Computing 52 (2023) 38–79.","apa":"Krokhin, A., Opršal, J., Wrochna, M., & Živný, S. (2023). Topology and adjunction in promise constraint satisfaction. SIAM Journal on Computing. Society for Industrial and Applied Mathematics. https://doi.org/10.1137/20m1378223"},"publication_status":"published","article_processing_charge":"No","publication_identifier":{"eissn":["1095-7111"],"issn":["0097-5397"]},"publisher":"Society for Industrial and Applied Mathematics","doi":"10.1137/20m1378223","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2003.11351","open_access":"1"}],"abstract":[{"lang":"eng","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."}],"article_type":"original","oa_version":"Preprint","day":"01","volume":52,"ec_funded":1,"external_id":{"arxiv":["2003.11351"],"isi":["000955000000001"]},"quality_controlled":"1","project":[{"call_identifier":"H2020","name":"IST-BRIDGE: International postdoctoral program","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","grant_number":"101034413"}]},{"article_type":"original","main_file_link":[{"open_access":"1","url":"https://hal-emse.ccsd.cnrs.fr/3IA-COTEDAZUR/hal-04083489v1"}],"abstract":[{"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. ","lang":"eng"}],"ec_funded":1,"oa_version":"Submitted Version","volume":52,"day":"30","external_id":{"isi":["001013183000012"]},"quality_controlled":"1","project":[{"grant_number":"754411","call_identifier":"H2020","name":"ISTplus - Postdoctoral Fellowships","_id":"260C2330-B435-11E9-9278-68D0E5697425"},{"name":"Learning and triangulating manifolds via collapses","_id":"fc390959-9c52-11eb-aca3-afa58bd282b2","grant_number":"M03073"}],"date_updated":"2025-04-15T06:54:46Z","month":"04","department":[{"_id":"HeEd"}],"isi":1,"title":"Tracing isomanifolds in Rd in time polynomial in d using Coxeter–Freudenthal–Kuhn triangulations","date_published":"2023-04-30T00:00:00Z","year":"2023","citation":{"apa":"Boissonnat, J. D., Kachanovich, S., & Wintraecken, M. (2023). Tracing isomanifolds in Rd in time polynomial in d using Coxeter–Freudenthal–Kuhn triangulations. SIAM Journal on Computing. Society for Industrial and Applied Mathematics. https://doi.org/10.1137/21M1412918","short":"J.D. Boissonnat, S. Kachanovich, M. Wintraecken, SIAM Journal on Computing 52 (2023) 452–486.","chicago":"Boissonnat, Jean Daniel, Siargey Kachanovich, and Mathijs Wintraecken. “Tracing Isomanifolds in Rd in Time Polynomial in d Using Coxeter–Freudenthal–Kuhn Triangulations.” SIAM Journal on Computing. Society for Industrial and Applied Mathematics, 2023. https://doi.org/10.1137/21M1412918.","ama":"Boissonnat JD, Kachanovich S, Wintraecken M. Tracing isomanifolds in Rd in time polynomial in d using Coxeter–Freudenthal–Kuhn triangulations. SIAM Journal on Computing. 2023;52(2):452-486. doi:10.1137/21M1412918","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.","mla":"Boissonnat, Jean Daniel, et al. “Tracing Isomanifolds in Rd in Time Polynomial in d Using Coxeter–Freudenthal–Kuhn Triangulations.” SIAM Journal on Computing, vol. 52, no. 2, Society for Industrial and Applied Mathematics, 2023, pp. 452–86, doi:10.1137/21M1412918.","ieee":"J. D. Boissonnat, S. Kachanovich, and M. Wintraecken, “Tracing isomanifolds in Rd in time polynomial in d using Coxeter–Freudenthal–Kuhn triangulations,” SIAM Journal on Computing, vol. 52, no. 2. Society for Industrial and Applied Mathematics, pp. 452–486, 2023."},"publisher":"Society for Industrial and Applied Mathematics","article_processing_charge":"No","publication_identifier":{"issn":["0097-5397"],"eissn":["1095-7111"]},"doi":"10.1137/21M1412918","publication_status":"published","page":"452-486","intvolume":" 52","scopus_import":"1","date_created":"2023-05-14T22:01:00Z","status":"public","publication":"SIAM Journal on Computing","language":[{"iso":"eng"}],"corr_author":"1","issue":"2","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","author":[{"last_name":"Boissonnat","full_name":"Boissonnat, Jean Daniel","first_name":"Jean Daniel"},{"first_name":"Siargey","last_name":"Kachanovich","full_name":"Kachanovich, Siargey"},{"first_name":"Mathijs","orcid":"0000-0002-7472-2220","full_name":"Wintraecken, Mathijs","id":"307CFBC8-F248-11E8-B48F-1D18A9856A87","last_name":"Wintraecken"}],"type":"journal_article","oa":1,"related_material":{"record":[{"relation":"earlier_version","id":"9441","status":"public"}]},"_id":"12960"},{"publication_status":"published","publication_identifier":{"eissn":["1095-7111"],"issn":["0097-5397"]},"article_processing_charge":"No","publisher":"Society for Industrial & Applied Mathematics","doi":"10.1137/16m1097808","date_published":"2021-05-01T00:00:00Z","year":"2021","citation":{"chicago":"Henzinger, Monika, Sebastian Krinninger, and Danupon Nanongkai. “A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths.” SIAM Journal on Computing. Society for Industrial & Applied Mathematics, 2021. https://doi.org/10.1137/16m1097808.","ama":"Henzinger M, Krinninger S, Nanongkai D. A deterministic almost-tight distributed algorithm for approximating single-source shortest paths. SIAM Journal on Computing. 2021;50(3):STOC16-98-STOC16-137. doi:10.1137/16m1097808","apa":"Henzinger, M., Krinninger, S., & Nanongkai, D. (2021). A deterministic almost-tight distributed algorithm for approximating single-source shortest paths. SIAM Journal on Computing. Society for Industrial & Applied Mathematics. https://doi.org/10.1137/16m1097808","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.” SIAM Journal on Computing, vol. 50, no. 3, Society for Industrial & Applied Mathematics, 2021, pp. STOC16-98-STOC16-137, doi:10.1137/16m1097808.","ieee":"M. Henzinger, S. Krinninger, and D. Nanongkai, “A deterministic almost-tight distributed algorithm for approximating single-source shortest paths,” SIAM Journal on Computing, vol. 50, no. 3. Society for Industrial & Applied Mathematics, pp. STOC16-98-STOC16-137, 2021.","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."},"title":"A deterministic almost-tight distributed algorithm for approximating single-source shortest paths","date_updated":"2024-11-06T12:22:31Z","month":"05","quality_controlled":"1","external_id":{"arxiv":["1504.07056"]},"oa_version":"Preprint","day":"01","volume":50,"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]."}],"main_file_link":[{"url":"https://arxiv.org/abs/1504.07056","open_access":"1"}],"article_type":"original","_id":"11886","arxiv":1,"oa":1,"extern":"1","author":[{"full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger","orcid":"0000-0002-5008-6530","first_name":"Monika H"},{"full_name":"Krinninger, Sebastian","last_name":"Krinninger","first_name":"Sebastian"},{"last_name":"Nanongkai","full_name":"Nanongkai, Danupon","first_name":"Danupon"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"journal_article","issue":"3","publication":"SIAM Journal on Computing","language":[{"iso":"eng"}],"status":"public","date_created":"2022-08-17T07:54:45Z","scopus_import":"1","page":"STOC16-98-STOC16-137","intvolume":" 50"},{"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","author":[{"last_name":"Czumaj","full_name":"Czumaj, Artur","first_name":"Artur"},{"full_name":"Davies, Peter","id":"11396234-BB50-11E9-B24C-90FCE5697425","last_name":"Davies","orcid":"0000-0002-5646-9524","first_name":"Peter"},{"last_name":"Parter","full_name":"Parter, Merav","first_name":"Merav"}],"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.","type":"journal_article","issue":"5","_id":"15271","page":"1603-1626","intvolume":" 50","publication":"SIAM Journal on Computing","language":[{"iso":"eng"}],"status":"public","keyword":["General Mathematics","General Computer Science"],"scopus_import":"1","date_created":"2024-04-03T07:53:22Z","isi":1,"title":"Simple, deterministic, constant-round coloring in congested clique and MPC","date_updated":"2025-09-10T10:14:11Z","month":"01","department":[{"_id":"DaAl"}],"publisher":"Society for Industrial and Applied Mathematics","publication_identifier":{"eissn":["1095-7111"],"issn":["0097-5397"]},"article_processing_charge":"No","doi":"10.1137/20m1366502","publication_status":"published","date_published":"2021-01-01T00:00:00Z","year":"2021","citation":{"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.","ieee":"A. Czumaj, P. Davies, and M. Parter, “Simple, deterministic, constant-round coloring in congested clique and MPC,” SIAM Journal on Computing, vol. 50, no. 5. Society for Industrial and Applied Mathematics, pp. 1603–1626, 2021.","mla":"Czumaj, Artur, et al. “Simple, Deterministic, Constant-Round Coloring in Congested Clique and MPC.” SIAM Journal on Computing, vol. 50, no. 5, Society for Industrial and Applied Mathematics, 2021, pp. 1603–26, doi:10.1137/20m1366502.","short":"A. Czumaj, P. Davies, M. Parter, SIAM Journal on Computing 50 (2021) 1603–1626.","apa":"Czumaj, A., Davies, P., & Parter, M. (2021). Simple, deterministic, constant-round coloring in congested clique and MPC. SIAM Journal on Computing. Society for Industrial and Applied Mathematics. https://doi.org/10.1137/20m1366502","ama":"Czumaj A, Davies P, Parter M. Simple, deterministic, constant-round coloring in congested clique and MPC. SIAM Journal on Computing. 2021;50(5):1603-1626. doi:10.1137/20m1366502","chicago":"Czumaj, Artur, Peter Davies, and Merav Parter. “Simple, Deterministic, Constant-Round Coloring in Congested Clique and MPC.” SIAM Journal on Computing. Society for Industrial and Applied Mathematics, 2021. https://doi.org/10.1137/20m1366502."},"article_type":"original","abstract":[{"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.","lang":"eng"}],"quality_controlled":"1","external_id":{"isi":["000713008600004"]},"project":[{"name":"ISTplus - Postdoctoral Fellowships","call_identifier":"H2020","_id":"260C2330-B435-11E9-9278-68D0E5697425","grant_number":"754411"}],"ec_funded":1,"day":"01","volume":50,"oa_version":"None"},{"main_file_link":[{"url":"https://arxiv.org/abs/1704.01254"}],"abstract":[{"lang":"eng","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."}],"article_type":"original","day":"01","oa_version":"Preprint","volume":49,"external_id":{"arxiv":["1704.01254"]},"quality_controlled":"1","month":"01","date_updated":"2024-11-06T12:22:42Z","title":"Local flow partitioning for faster edge connectivity","citation":{"ieee":"M. Henzinger, S. Rao, and D. Wang, “Local flow partitioning for faster edge connectivity,” SIAM Journal on Computing, vol. 49, no. 1. Society for Industrial & Applied Mathematics, pp. 1–36, 2020.","mla":"Henzinger, Monika, et al. “Local Flow Partitioning for Faster Edge Connectivity.” SIAM Journal on Computing, vol. 49, no. 1, Society for Industrial & Applied Mathematics, 2020, pp. 1–36, doi:10.1137/18m1180335.","ista":"Henzinger M, Rao S, Wang D. 2020. Local flow partitioning for faster edge connectivity. SIAM Journal on Computing. 49(1), 1–36.","ama":"Henzinger M, Rao S, Wang D. Local flow partitioning for faster edge connectivity. SIAM Journal on Computing. 2020;49(1):1-36. doi:10.1137/18m1180335","chicago":"Henzinger, Monika, Satish Rao, and Di Wang. “Local Flow Partitioning for Faster Edge Connectivity.” SIAM Journal on Computing. Society for Industrial & Applied Mathematics, 2020. https://doi.org/10.1137/18m1180335.","short":"M. Henzinger, S. Rao, D. Wang, SIAM Journal on Computing 49 (2020) 1–36.","apa":"Henzinger, M., Rao, S., & Wang, D. (2020). Local flow partitioning for faster edge connectivity. SIAM Journal on Computing. Society for Industrial & Applied Mathematics. https://doi.org/10.1137/18m1180335"},"year":"2020","date_published":"2020-01-01T00:00:00Z","publication_status":"published","doi":"10.1137/18m1180335","publisher":"Society for Industrial & Applied Mathematics","article_processing_charge":"No","publication_identifier":{"issn":["0097-5397"],"eissn":["1095-7111"]},"page":"1-36","intvolume":" 49","date_created":"2022-08-17T08:09:31Z","status":"public","scopus_import":"1","language":[{"iso":"eng"}],"publication":"SIAM Journal on Computing","issue":"1","extern":"1","type":"journal_article","author":[{"orcid":"0000-0002-5008-6530","first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H","last_name":"Henzinger"},{"first_name":"Satish","full_name":"Rao, Satish","last_name":"Rao"},{"first_name":"Di","last_name":"Wang","full_name":"Wang, Di"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","related_material":{"record":[{"status":"public","id":"11873","relation":"later_version"}]},"_id":"11889","arxiv":1},{"month":"05","date_updated":"2021-01-12T08:08:30Z","title":"Anisotropic triangulations via discrete Riemannian Voronoi diagrams","citation":{"short":"J.-D. Boissonnat, M. Rouxel-Labbé, M. Wintraecken, SIAM Journal on Computing 48 (2019) 1046–1097.","apa":"Boissonnat, J.-D., Rouxel-Labbé, M., & Wintraecken, M. (2019). Anisotropic triangulations via discrete Riemannian Voronoi diagrams. SIAM Journal on Computing. Society for Industrial & Applied Mathematics (SIAM). https://doi.org/10.1137/17m1152292","ama":"Boissonnat J-D, Rouxel-Labbé M, Wintraecken M. Anisotropic triangulations via discrete Riemannian Voronoi diagrams. SIAM Journal on Computing. 2019;48(3):1046-1097. doi:10.1137/17m1152292","chicago":"Boissonnat, Jean-Daniel, Mael Rouxel-Labbé, and Mathijs Wintraecken. “Anisotropic Triangulations via Discrete Riemannian Voronoi Diagrams.” SIAM Journal on Computing. Society for Industrial & Applied Mathematics (SIAM), 2019. https://doi.org/10.1137/17m1152292.","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.","ieee":"J.-D. Boissonnat, M. Rouxel-Labbé, and M. Wintraecken, “Anisotropic triangulations via discrete Riemannian Voronoi diagrams,” SIAM Journal on Computing, vol. 48, no. 3. Society for Industrial & Applied Mathematics (SIAM), pp. 1046–1097, 2019.","mla":"Boissonnat, Jean-Daniel, et al. “Anisotropic Triangulations via Discrete Riemannian Voronoi Diagrams.” SIAM Journal on Computing, vol. 48, no. 3, Society for Industrial & Applied Mathematics (SIAM), 2019, pp. 1046–97, doi:10.1137/17m1152292."},"date_published":"2019-05-21T00:00:00Z","year":"2019","doi":"10.1137/17m1152292","publication_identifier":{"eissn":["1095-7111"],"issn":["0097-5397"]},"publisher":"Society for Industrial & Applied Mathematics (SIAM)","publication_status":"published","abstract":[{"lang":"eng","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."}],"main_file_link":[{"url":"https://arxiv.org/abs/1703.06487","open_access":"1"}],"oa_version":"Preprint","volume":48,"day":"21","quality_controlled":"1","external_id":{"arxiv":["1703.06487"]},"issue":"3","type":"journal_article","author":[{"first_name":"Jean-Daniel","full_name":"Boissonnat, Jean-Daniel","last_name":"Boissonnat"},{"first_name":"Mael","last_name":"Rouxel-Labbé","full_name":"Rouxel-Labbé, Mael"},{"id":"307CFBC8-F248-11E8-B48F-1D18A9856A87","full_name":"Wintraecken, Mathijs","last_name":"Wintraecken","orcid":"0000-0002-7472-2220","first_name":"Mathijs"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","extern":"1","oa":1,"arxiv":1,"_id":"6672","intvolume":" 48","page":"1046-1097","status":"public","date_created":"2019-07-24T08:42:12Z","language":[{"iso":"eng"}],"publication":"SIAM Journal on Computing"},{"arxiv":1,"_id":"7412","oa":1,"type":"journal_article","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","author":[{"first_name":"Dimitris","full_name":"Achlioptas, Dimitris","last_name":"Achlioptas"},{"first_name":"Fotis","full_name":"Iliopoulos, Fotis","last_name":"Iliopoulos"},{"last_name":"Kolmogorov","full_name":"Kolmogorov, Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","first_name":"Vladimir"}],"issue":"5","language":[{"iso":"eng"}],"publication":"SIAM Journal on Computing","status":"public","date_created":"2020-01-30T09:27:32Z","scopus_import":"1","intvolume":" 48","page":"1583-1602","doi":"10.1137/16m109332x","article_processing_charge":"No","publisher":"SIAM","publication_identifier":{"issn":["0097-5397"],"eissn":["1095-7111"]},"publication_status":"published","citation":{"short":"D. Achlioptas, F. Iliopoulos, V. Kolmogorov, SIAM Journal on Computing 48 (2019) 1583–1602.","apa":"Achlioptas, D., Iliopoulos, F., & Kolmogorov, V. (2019). A local lemma for focused stochastical algorithms. SIAM Journal on Computing. SIAM. https://doi.org/10.1137/16m109332x","ama":"Achlioptas D, Iliopoulos F, Kolmogorov V. A local lemma for focused stochastical algorithms. SIAM Journal on Computing. 2019;48(5):1583-1602. doi:10.1137/16m109332x","chicago":"Achlioptas, Dimitris, Fotis Iliopoulos, and Vladimir Kolmogorov. “A Local Lemma for Focused Stochastical Algorithms.” SIAM Journal on Computing. SIAM, 2019. https://doi.org/10.1137/16m109332x.","ista":"Achlioptas D, Iliopoulos F, Kolmogorov V. 2019. A local lemma for focused stochastical algorithms. SIAM Journal on Computing. 48(5), 1583–1602.","ieee":"D. Achlioptas, F. Iliopoulos, and V. Kolmogorov, “A local lemma for focused stochastical algorithms,” SIAM Journal on Computing, vol. 48, no. 5. SIAM, pp. 1583–1602, 2019.","mla":"Achlioptas, Dimitris, et al. “A Local Lemma for Focused Stochastical Algorithms.” SIAM Journal on Computing, vol. 48, no. 5, SIAM, 2019, pp. 1583–602, doi:10.1137/16m109332x."},"date_published":"2019-10-31T00:00:00Z","year":"2019","isi":1,"title":"A local lemma for focused stochastical algorithms","department":[{"_id":"VlKo"}],"month":"10","date_updated":"2024-11-04T13:52:36Z","project":[{"_id":"25FBA906-B435-11E9-9278-68D0E5697425","name":"Discrete Optimization in Computer Vision: Theory and Practice","call_identifier":"FP7","grant_number":"616160"}],"external_id":{"arxiv":["1809.01537"],"isi":["000493900200005"]},"quality_controlled":"1","ec_funded":1,"oa_version":"Preprint","day":"31","volume":48,"article_type":"original","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."}],"main_file_link":[{"url":"https://arxiv.org/abs/1809.01537","open_access":"1"}]},{"page":"859-887","intvolume":" 47","date_created":"2022-08-17T08:21:23Z","scopus_import":"1","status":"public","language":[{"iso":"eng"}],"publication":"SIAM Journal on Computing","issue":"3","extern":"1","type":"journal_article","author":[{"first_name":"Sayan","last_name":"Bhattacharya","full_name":"Bhattacharya, Sayan"},{"last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H","first_name":"Monika H","orcid":"0000-0002-5008-6530"},{"last_name":"Italiano","full_name":"Italiano, Giuseppe F.","first_name":"Giuseppe F."}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","related_material":{"record":[{"status":"public","id":"11875","relation":"earlier_version"}]},"oa":1,"_id":"11890","arxiv":1,"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1412.1318"}],"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"}],"article_type":"original","day":"01","oa_version":"Preprint","volume":47,"external_id":{"arxiv":["1412.1318"]},"quality_controlled":"1","month":"05","date_updated":"2024-11-06T12:22:54Z","title":"Deterministic fully dynamic data structures for vertex cover and matching","citation":{"ieee":"S. Bhattacharya, M. Henzinger, and G. F. Italiano, “Deterministic fully dynamic data structures for vertex cover and matching,” SIAM Journal on Computing, vol. 47, no. 3. Society for Industrial & Applied Mathematics, pp. 859–887, 2018.","mla":"Bhattacharya, Sayan, et al. “Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching.” SIAM Journal on Computing, vol. 47, no. 3, Society for Industrial & Applied Mathematics, 2018, pp. 859–87, doi:10.1137/140998925.","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.","ama":"Bhattacharya S, Henzinger M, Italiano GF. Deterministic fully dynamic data structures for vertex cover and matching. SIAM Journal on Computing. 2018;47(3):859-887. doi:10.1137/140998925","chicago":"Bhattacharya, Sayan, Monika Henzinger, and Giuseppe F. Italiano. “Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching.” SIAM Journal on Computing. Society for Industrial & Applied Mathematics, 2018. https://doi.org/10.1137/140998925.","short":"S. Bhattacharya, M. Henzinger, G.F. Italiano, SIAM Journal on Computing 47 (2018) 859–887.","apa":"Bhattacharya, S., Henzinger, M., & Italiano, G. F. (2018). Deterministic fully dynamic data structures for vertex cover and matching. SIAM Journal on Computing. Society for Industrial & Applied Mathematics. https://doi.org/10.1137/140998925"},"year":"2018","date_published":"2018-05-01T00:00:00Z","publication_status":"published","doi":"10.1137/140998925","article_processing_charge":"No","publisher":"Society for Industrial & Applied Mathematics","publication_identifier":{"eissn":["1095-7111"],"issn":["0097-5397"]}},{"publication":"SIAM Journal on Computing","language":[{"iso":"eng"}],"date_created":"2019-02-13T12:59:33Z","scopus_import":"1","status":"public","intvolume":" 47","page":"2029-2056","arxiv":1,"_id":"5975","oa":1,"related_material":{"record":[{"id":"1193","status":"public","relation":"earlier_version"}]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"last_name":"Kolmogorov","full_name":"Kolmogorov, Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","first_name":"Vladimir"}],"type":"journal_article","issue":"6","quality_controlled":"1","external_id":{"isi":["000453785100001"],"arxiv":["1506.08547"]},"project":[{"grant_number":"616160","_id":"25FBA906-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"Discrete Optimization in Computer Vision: Theory and Practice"}],"ec_funded":1,"volume":47,"oa_version":"Preprint","day":"08","main_file_link":[{"url":"https://arxiv.org/abs/1506.08547","open_access":"1"}],"abstract":[{"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.","lang":"eng"}],"article_processing_charge":"No","publisher":"Society for Industrial and Applied Mathematics","publication_identifier":{"eissn":["1095-7111"],"issn":["0097-5397"]},"doi":"10.1137/16m1093306","publication_status":"published","date_published":"2018-11-08T00:00:00Z","year":"2018","citation":{"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.” SIAM Journal on Computing, vol. 47, no. 6, Society for Industrial and Applied Mathematics, 2018, pp. 2029–56, doi:10.1137/16m1093306.","ieee":"V. Kolmogorov, “Commutativity in the algorithmic Lovász local lemma,” SIAM Journal on Computing, vol. 47, no. 6. Society for Industrial and Applied Mathematics, pp. 2029–2056, 2018.","apa":"Kolmogorov, V. (2018). Commutativity in the algorithmic Lovász local lemma. SIAM Journal on Computing. Society for Industrial and Applied Mathematics. https://doi.org/10.1137/16m1093306","short":"V. Kolmogorov, SIAM Journal on Computing 47 (2018) 2029–2056.","chicago":"Kolmogorov, Vladimir. “Commutativity in the Algorithmic Lovász Local Lemma.” SIAM Journal on Computing. Society for Industrial and Applied Mathematics, 2018. https://doi.org/10.1137/16m1093306.","ama":"Kolmogorov V. Commutativity in the algorithmic Lovász local lemma. SIAM Journal on Computing. 2018;47(6):2029-2056. doi:10.1137/16m1093306"},"isi":1,"title":"Commutativity in the algorithmic Lovász local lemma","date_updated":"2025-09-22T09:44:20Z","month":"11","department":[{"_id":"VlKo"}]},{"oa":1,"arxiv":1,"_id":"11891","issue":"3","author":[{"last_name":"Henzinger","full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530","first_name":"Monika H"},{"first_name":"Sebastian","last_name":"Krinninger","full_name":"Krinninger, Sebastian"},{"full_name":"Nanongkai, Danupon","last_name":"Nanongkai","first_name":"Danupon"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"journal_article","extern":"1","status":"public","date_created":"2022-08-17T08:37:00Z","scopus_import":"1","publication":"SIAM Journal on Computing","language":[{"iso":"eng"}],"intvolume":" 45","page":"947-1006","year":"2016","date_published":"2016-05-01T00:00:00Z","citation":{"ieee":"M. Henzinger, S. Krinninger, and D. Nanongkai, “Dynamic approximate all-pairs shortest paths: Breaking the O(mn) barrier and derandomization,” SIAM Journal on Computing, vol. 45, no. 3. Society for Industrial & Applied Mathematics, pp. 947–1006, 2016.","mla":"Henzinger, Monika, et al. “Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(Mn) Barrier and Derandomization.” SIAM Journal on Computing, vol. 45, no. 3, Society for Industrial & Applied Mathematics, 2016, pp. 947–1006, doi:10.1137/140957299.","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.","ama":"Henzinger M, Krinninger S, Nanongkai D. Dynamic approximate all-pairs shortest paths: Breaking the O(mn) barrier and derandomization. SIAM Journal on Computing. 2016;45(3):947-1006. doi:10.1137/140957299","chicago":"Henzinger, Monika, Sebastian Krinninger, and Danupon Nanongkai. “Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(Mn) Barrier and Derandomization.” SIAM Journal on Computing. Society for Industrial & Applied Mathematics, 2016. https://doi.org/10.1137/140957299.","short":"M. Henzinger, S. Krinninger, D. Nanongkai, SIAM Journal on Computing 45 (2016) 947–1006.","apa":"Henzinger, M., Krinninger, S., & Nanongkai, D. (2016). Dynamic approximate all-pairs shortest paths: Breaking the O(mn) barrier and derandomization. SIAM Journal on Computing. Society for Industrial & Applied Mathematics. https://doi.org/10.1137/140957299"},"article_processing_charge":"No","publisher":"Society for Industrial & Applied Mathematics","publication_identifier":{"eissn":["1095-7111"],"issn":["0097-5397"]},"doi":"10.1137/140957299","publication_status":"published","date_updated":"2024-11-06T12:23:06Z","month":"05","title":"Dynamic approximate all-pairs shortest paths: Breaking the O(mn) barrier and derandomization","volume":45,"day":"01","oa_version":"Preprint","external_id":{"arxiv":["1308.0776"]},"quality_controlled":"1","article_type":"original","abstract":[{"lang":"eng","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."}],"main_file_link":[{"url":"https://arxiv.org/abs/1308.0776","open_access":"1"}]},{"page":"364-374","intvolume":" 31","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"}],"article_type":"original","quality_controlled":"1","language":[{"iso":"eng"}],"publication":"SIAM Journal on Computing","volume":31,"oa_version":"None","day":"01","status":"public","scopus_import":"1","date_created":"2022-08-17T08:43:43Z","extern":"1","title":"Maintaining minimum spanning forests in dynamic graphs","type":"journal_article","author":[{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H","last_name":"Henzinger","orcid":"0000-0002-5008-6530","first_name":"Monika H"},{"first_name":"Valerie","full_name":"King, Valerie","last_name":"King"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","issue":"2","month":"03","date_updated":"2024-11-06T12:23:16Z","publication_status":"published","_id":"11892","doi":"10.1137/s0097539797327209","publication_identifier":{"issn":["0097-5397"],"eissn":["1095-7111"]},"article_processing_charge":"No","publisher":"Society for Industrial & Applied Mathematics","citation":{"ieee":"M. Henzinger and V. King, “Maintaining minimum spanning forests in dynamic graphs,” SIAM Journal on Computing, vol. 31, no. 2. Society for Industrial & Applied Mathematics, pp. 364–374, 2001.","mla":"Henzinger, Monika, and Valerie King. “Maintaining Minimum Spanning Forests in Dynamic Graphs.” SIAM Journal on Computing, vol. 31, no. 2, Society for Industrial & Applied Mathematics, 2001, pp. 364–74, doi:10.1137/s0097539797327209.","ista":"Henzinger M, King V. 2001. Maintaining minimum spanning forests in dynamic graphs. SIAM Journal on Computing. 31(2), 364–374.","ama":"Henzinger M, King V. Maintaining minimum spanning forests in dynamic graphs. SIAM Journal on Computing. 2001;31(2):364-374. doi:10.1137/s0097539797327209","chicago":"Henzinger, Monika, and Valerie King. “Maintaining Minimum Spanning Forests in Dynamic Graphs.” SIAM Journal on Computing. Society for Industrial & Applied Mathematics, 2001. https://doi.org/10.1137/s0097539797327209.","short":"M. Henzinger, V. King, SIAM Journal on Computing 31 (2001) 364–374.","apa":"Henzinger, M., & King, V. (2001). Maintaining minimum spanning forests in dynamic graphs. SIAM Journal on Computing. Society for Industrial & Applied Mathematics. https://doi.org/10.1137/s0097539797327209"},"year":"2001","date_published":"2001-03-01T00:00:00Z"},{"quality_controlled":"1","volume":29,"day":"01","oa_version":"None","conference":{"name":"STOC97: 29th Annual Symposium on Theory of Computing","end_date":"1997-05-06","location":"El Paso, TX, United States","start_date":"1997-05-04"},"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."}],"article_type":"original","publication_status":"published","doi":"10.1137/s009753979732428x","publisher":"Society for Industrial and Applied Mathematics","article_processing_charge":"No","publication_identifier":{"issn":["0097-5397"],"eissn":["1095-7111"]},"citation":{"ama":"Albers S, Henzinger M. Exploring unknown environments. SIAM Journal on Computing. 2000;29(4):1164-1188. doi:10.1137/s009753979732428x","chicago":"Albers, Susanne, and Monika Henzinger. “Exploring Unknown Environments.” SIAM Journal on Computing. Society for Industrial and Applied Mathematics, 2000. https://doi.org/10.1137/s009753979732428x.","short":"S. Albers, M. Henzinger, SIAM Journal on Computing 29 (2000) 1164–1188.","apa":"Albers, S., & Henzinger, M. (2000). Exploring unknown environments. SIAM Journal on Computing. El Paso, TX, United States: Society for Industrial and Applied Mathematics. https://doi.org/10.1137/s009753979732428x","ieee":"S. Albers and M. Henzinger, “Exploring unknown environments,” SIAM Journal on Computing, vol. 29, no. 4. Society for Industrial and Applied Mathematics, pp. 1164–1188, 2000.","mla":"Albers, Susanne, and Monika Henzinger. “Exploring Unknown Environments.” SIAM Journal on Computing, vol. 29, no. 4, Society for Industrial and Applied Mathematics, 2000, pp. 1164–88, doi:10.1137/s009753979732428x.","ista":"Albers S, Henzinger M. 2000. Exploring unknown environments. SIAM Journal on Computing. 29(4), 1164–1188."},"year":"2000","date_published":"2000-07-01T00:00:00Z","title":"Exploring unknown environments","month":"07","date_updated":"2024-11-06T12:09:07Z","language":[{"iso":"eng"}],"publication":"SIAM Journal on Computing","status":"public","scopus_import":"1","keyword":["directed graph","exploration algorithm"],"date_created":"2022-07-29T09:04:36Z","page":"1164-1188","intvolume":" 29","_id":"11694","extern":"1","type":"journal_article","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.","author":[{"full_name":"Albers, Susanne","last_name":"Albers","first_name":"Susanne"},{"orcid":"0000-0002-5008-6530","first_name":"Monika H","full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","issue":"4"},{"date_published":"2000-11-01T00:00:00Z","year":"2000","citation":{"chicago":"Henzinger, Monika. “Improved Data Structures for Fully Dynamic Biconnectivity.” SIAM Journal on Computing. Society for Industrial & Applied Mathematics, 2000. https://doi.org/10.1137/s0097539794263907.","ama":"Henzinger M. Improved data structures for fully dynamic biconnectivity. SIAM Journal on Computing. 2000;29(6):1761-1815. doi:10.1137/s0097539794263907","apa":"Henzinger, M. (2000). Improved data structures for fully dynamic biconnectivity. SIAM Journal on Computing. Society for Industrial & Applied Mathematics. https://doi.org/10.1137/s0097539794263907","short":"M. Henzinger, SIAM Journal on Computing 29 (2000) 1761–1815.","mla":"Henzinger, Monika. “Improved Data Structures for Fully Dynamic Biconnectivity.” SIAM Journal on Computing, vol. 29, no. 6, Society for Industrial & Applied Mathematics, 2000, pp. 1761–815, doi:10.1137/s0097539794263907.","ieee":"M. Henzinger, “Improved data structures for fully dynamic biconnectivity,” SIAM Journal on Computing, vol. 29, no. 6. Society for Industrial & Applied Mathematics, pp. 1761–1815, 2000.","ista":"Henzinger M. 2000. Improved data structures for fully dynamic biconnectivity. SIAM Journal on Computing. 29(6), 1761–1815."},"_id":"11893","publication_status":"published","publication_identifier":{"issn":["0097-5397"],"eissn":["1095-7111"]},"article_processing_charge":"No","publisher":"Society for Industrial & Applied Mathematics","doi":"10.1137/s0097539794263907","date_updated":"2024-11-06T12:00:56Z","month":"11","issue":"6","title":"Improved data structures for fully dynamic biconnectivity","extern":"1","author":[{"last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","first_name":"Monika H"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"journal_article","day":"01","volume":29,"oa_version":"None","scopus_import":"1","status":"public","date_created":"2022-08-17T08:45:41Z","quality_controlled":"1","publication":"SIAM Journal on Computing","language":[{"iso":"eng"}],"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"}],"article_type":"original","intvolume":" 29","page":"1761-1815"},{"title":"An O(n^2 log n) time algorithm for the MinMax angle triangulation","date_updated":"2022-03-16T09:35:05Z","month":"07","publication_identifier":{"issn":["0097-5397"],"eissn":["1095-7111"]},"article_processing_charge":"No","publisher":"Society for Industrial and Applied Mathematics ","doi":"10.1137/0913058","publication_status":"published","date_published":"1992-07-01T00:00:00Z","year":"1992","citation":{"ieee":"H. Edelsbrunner, T. Tan, and R. Waupotitsch, “An O(n^2 log n) time algorithm for the MinMax angle triangulation,” SIAM Journal on Scientific Computing, vol. 13, no. 4. Society for Industrial and Applied Mathematics , pp. 994–1008, 1992.","mla":"Edelsbrunner, Herbert, et al. “An O(N^2 Log n) Time Algorithm for the MinMax Angle Triangulation.” SIAM Journal on Scientific Computing, vol. 13, no. 4, Society for Industrial and Applied Mathematics , 1992, pp. 994–1008, doi:10.1137/0913058.","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.","ama":"Edelsbrunner H, Tan T, Waupotitsch R. An O(n^2 log n) time algorithm for the MinMax angle triangulation. SIAM Journal on Scientific Computing. 1992;13(4):994-1008. doi:10.1137/0913058","chicago":"Edelsbrunner, Herbert, Tiow Tan, and Roman Waupotitsch. “An O(N^2 Log n) Time Algorithm for the MinMax Angle Triangulation.” SIAM Journal on Scientific Computing. Society for Industrial and Applied Mathematics , 1992. https://doi.org/10.1137/0913058.","short":"H. Edelsbrunner, T. Tan, R. Waupotitsch, SIAM Journal on Scientific Computing 13 (1992) 994–1008.","apa":"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. Society for Industrial and Applied Mathematics . https://doi.org/10.1137/0913058"},"article_type":"original","abstract":[{"lang":"eng","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."}],"main_file_link":[{"url":"https://epubs.siam.org/doi/10.1137/0913058"}],"quality_controlled":"1","day":"01","volume":13,"oa_version":"None","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","author":[{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","full_name":"Edelsbrunner, Herbert","last_name":"Edelsbrunner","orcid":"0000-0002-9823-6833","first_name":"Herbert"},{"last_name":"Tan","full_name":"Tan, Tiow","first_name":"Tiow"},{"first_name":"Roman","last_name":"Waupotitsch","full_name":"Waupotitsch, Roman"}],"type":"journal_article","extern":"1","issue":"4","_id":"4043","publist_id":"2081","page":"994 - 1008","intvolume":" 13","publication":"SIAM Journal on Scientific Computing","language":[{"iso":"eng"}],"status":"public","date_created":"2018-12-11T12:06:36Z"},{"year":"1991","date_published":"1991-04-01T00:00:00Z","citation":{"chicago":"Edelsbrunner, Herbert, and Weiping Shi. “An O(n Log^2 h) Time Algorithm for the Three-Dimensional Convex Hull Problem.” SIAM Journal on Computing. SIAM, 1991. https://doi.org/10.1137/0220016 .","ama":"Edelsbrunner H, Shi W. An O(n log^2 h) time algorithm for the three-dimensional convex hull problem. SIAM Journal on Computing. 1991;20(2):259-269. doi:10.1137/0220016 ","apa":"Edelsbrunner, H., & Shi, W. (1991). An O(n log^2 h) time algorithm for the three-dimensional convex hull problem. SIAM Journal on Computing. SIAM. https://doi.org/10.1137/0220016 ","short":"H. Edelsbrunner, W. Shi, SIAM Journal on Computing 20 (1991) 259–269.","mla":"Edelsbrunner, Herbert, and Weiping Shi. “An O(n Log^2 h) Time Algorithm for the Three-Dimensional Convex Hull Problem.” SIAM Journal on Computing, vol. 20, no. 2, SIAM, 1991, pp. 259–69, doi:10.1137/0220016 .","ieee":"H. Edelsbrunner and W. Shi, “An O(n log^2 h) time algorithm for the three-dimensional convex hull problem,” SIAM Journal on Computing, vol. 20, no. 2. SIAM, pp. 259–269, 1991.","ista":"Edelsbrunner H, Shi W. 1991. An O(n log^2 h) time algorithm for the three-dimensional convex hull problem. SIAM Journal on Computing. 20(2), 259–269."},"publication_status":"published","publisher":"SIAM","article_processing_charge":"No","publication_identifier":{"issn":["0097-5397"],"eissn":["1095-7111"]},"doi":"10.1137/0220016 ","date_updated":"2022-03-02T10:18:31Z","month":"04","title":"An O(n log^2 h) time algorithm for the three-dimensional convex hull problem","oa_version":"None","volume":20,"day":"01","quality_controlled":"1","main_file_link":[{"url":"https://epubs.siam.org/doi/10.1137/0220016"}],"abstract":[{"text":"An algorithm is presented that constructs the convex hull of a set of n points in three dimensions in worst-case time O(n log2h) and storage O(n), where h is the number of extreme points. This is an improvement of the O(nh) time gift-wrapping algorithm and, for certain values of h, of the O(n log n) time divide-and-conquer algorithm.","lang":"eng"}],"article_type":"original","_id":"4051","issue":"2","extern":"1","author":[{"full_name":"Edelsbrunner, Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","last_name":"Edelsbrunner","orcid":"0000-0002-9823-6833","first_name":"Herbert"},{"full_name":"Shi, Weiping","last_name":"Shi","first_name":"Weiping"}],"user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","type":"journal_article","date_created":"2018-12-11T12:06:39Z","status":"public","publication":"SIAM Journal on Computing","language":[{"iso":"eng"}],"page":"259 - 269","intvolume":" 20","publist_id":"2072"},{"_id":"4083","oa":1,"type":"journal_article","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","author":[{"first_name":"F.","full_name":"Yao, F.","last_name":"Yao"},{"last_name":"Dobkin","full_name":"Dobkin, David","first_name":"David"},{"last_name":"Edelsbrunner","full_name":"Edelsbrunner, Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833","first_name":"Herbert"},{"first_name":"Michael","last_name":"Paterson","full_name":"Paterson, Michael"}],"extern":"1","issue":"2","language":[{"iso":"eng"}],"publication":"SIAM Journal on Computing","scopus_import":"1","date_created":"2018-12-11T12:06:50Z","status":"public","publist_id":"2040","intvolume":" 18","page":"371 - 384","doi":"10.1137/0218025","publisher":"SIAM","article_processing_charge":"No","publication_identifier":{"issn":["0097-5397"],"eissn":["1095-7111"]},"publication_status":"published","citation":{"apa":"Yao, F., Dobkin, D., Edelsbrunner, H., & Paterson, M. (1989). Partitioning space for range queries. SIAM Journal on Computing. SIAM. https://doi.org/10.1137/0218025","short":"F. Yao, D. Dobkin, H. Edelsbrunner, M. Paterson, SIAM Journal on Computing 18 (1989) 371–384.","chicago":"Yao, F., David Dobkin, Herbert Edelsbrunner, and Michael Paterson. “Partitioning Space for Range Queries.” SIAM Journal on Computing. SIAM, 1989. https://doi.org/10.1137/0218025.","ama":"Yao F, Dobkin D, Edelsbrunner H, Paterson M. Partitioning space for range queries. SIAM Journal on Computing. 1989;18(2):371-384. doi:10.1137/0218025","ista":"Yao F, Dobkin D, Edelsbrunner H, Paterson M. 1989. Partitioning space for range queries. SIAM Journal on Computing. 18(2), 371–384.","mla":"Yao, F., et al. “Partitioning Space for Range Queries.” SIAM Journal on Computing, vol. 18, no. 2, SIAM, 1989, pp. 371–84, doi:10.1137/0218025.","ieee":"F. Yao, D. Dobkin, H. Edelsbrunner, and M. Paterson, “Partitioning space for range queries,” SIAM Journal on Computing, vol. 18, no. 2. SIAM, pp. 371–384, 1989."},"date_published":"1989-04-01T00:00:00Z","year":"1989","title":"Partitioning space for range queries","month":"04","date_updated":"2022-02-11T07:55:48Z","quality_controlled":"1","volume":18,"oa_version":"Published Version","day":"01","article_type":"original","main_file_link":[{"open_access":"1","url":"https://epubs.siam.org/doi/10.1137/0218025"}],"abstract":[{"text":"It is shown that, given a set S of n points in $R^3 $, one can always find three planes that form an eight-partition of S, that is, a partition where at most ${n / 8}$ points of S lie in each of the eight open regions. This theorem is used to define a data structure, called an octant tree, for representing any point set in $R^3 $. An octant tree for n points occupies $O(n)$ space and can be constructed in polynomial time. With this data structure and its refinements, efficient solutions to various range query problems in two and three dimensions can be obtained, including (1) half-space queries: find all points of S that lie to one side of any given plane; (2) polyhedron queries: find all points that lie inside (outside) any given polyhedron; and (3) circle queries in $R^2 $: for a planar set S, find all points that lie inside (outside) any given circle. The retrieval time for all these queries is $T(n) = O(n^\\alpha + m)$, where $\\alpha = 0.8988$ (or 0.8471 in case (3)), and m is the size of the output. This performance is the best currently known for linear-space data structures that can be deterministically constructed in polynomial time.","lang":"eng"}]},{"article_processing_charge":"No","publisher":"SIAM","publication_identifier":{"eissn":["1095-7111"],"issn":["0097-5397"]},"doi":"10.1137/0217054 ","publication_status":"published","year":"1988","date_published":"1988-01-01T00:00:00Z","citation":{"short":"H. Edelsbrunner, S. Skiena, SIAM Journal on Computing 17 (1988) 870–882.","apa":"Edelsbrunner, H., & Skiena, S. (1988). Probing convex polygons with X-Rays. SIAM Journal on Computing. SIAM. https://doi.org/10.1137/0217054 ","ama":"Edelsbrunner H, Skiena S. Probing convex polygons with X-Rays. SIAM Journal on Computing. 1988;17(5):870-882. doi:10.1137/0217054 ","chicago":"Edelsbrunner, Herbert, and Steven Skiena. “Probing Convex Polygons with X-Rays.” SIAM Journal on Computing. SIAM, 1988. https://doi.org/10.1137/0217054 .","ista":"Edelsbrunner H, Skiena S. 1988. Probing convex polygons with X-Rays. SIAM Journal on Computing. 17(5), 870–882.","ieee":"H. Edelsbrunner and S. Skiena, “Probing convex polygons with X-Rays,” SIAM Journal on Computing, vol. 17, no. 5. SIAM, pp. 870–882, 1988.","mla":"Edelsbrunner, Herbert, and Steven Skiena. “Probing Convex Polygons with X-Rays.” SIAM Journal on Computing, vol. 17, no. 5, SIAM, 1988, pp. 870–82, doi:10.1137/0217054 ."},"title":"Probing convex polygons with X-Rays","date_updated":"2022-02-08T11:14:23Z","month":"01","quality_controlled":"1","volume":17,"oa_version":"None","day":"01","article_type":"original","main_file_link":[{"url":"https://epubs.siam.org/doi/10.1137/0217054"}],"abstract":[{"text":"An X-ray probe through a polygon measures the length of intersection between a line and the polygon. This paper considers the properties of various classes of X-ray probes, and shows how they interact to give finite strategies for completely describing convex n-gons. It is shown that (3n/2)+6 probes are sufficient to verify a specified n-gon, while for determining convex polygons (3n-1)/2 X-ray probes are necesssary and 5n+O(1) sufficient, with 3n+O(1) sufficient given that a lower bound on the size of the smallest edge of P is known.","lang":"eng"}],"_id":"4091","author":[{"orcid":"0000-0002-9823-6833","first_name":"Herbert","last_name":"Edelsbrunner","full_name":"Edelsbrunner, Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Skiena","full_name":"Skiena, Steven","first_name":"Steven"}],"acknowledgement":"The research of this author was supported by the Amoco Foundation Facility for the Development of Computer Science 1-6-44862.","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","type":"journal_article","extern":"1","issue":"5","publication":"SIAM Journal on Computing","language":[{"iso":"eng"}],"status":"public","date_created":"2018-12-11T12:06:53Z","scopus_import":"1","publist_id":"2030","page":"870 - 882","intvolume":" 17"},{"publication_status":"published","doi":"10.1137/0215023","publisher":"SIAM","article_processing_charge":"No","publication_identifier":{"eissn":["1095-7111"],"issn":["0097-5397"]},"citation":{"ista":"Edelsbrunner H, Guibas L, Stolfi J. 1986. Optimal point location in a monotone subdivision. SIAM Journal on Computing. 15(2), 317–340.","mla":"Edelsbrunner, Herbert, et al. “Optimal Point Location in a Monotone Subdivision.” SIAM Journal on Computing, vol. 15, no. 2, SIAM, 1986, pp. 317–40, doi:10.1137/0215023.","ieee":"H. Edelsbrunner, L. Guibas, and J. Stolfi, “Optimal point location in a monotone subdivision,” SIAM Journal on Computing, vol. 15, no. 2. SIAM, pp. 317–340, 1986.","apa":"Edelsbrunner, H., Guibas, L., & Stolfi, J. (1986). Optimal point location in a monotone subdivision. SIAM Journal on Computing. SIAM. https://doi.org/10.1137/0215023","short":"H. Edelsbrunner, L. Guibas, J. Stolfi, SIAM Journal on Computing 15 (1986) 317–340.","chicago":"Edelsbrunner, Herbert, Leonidas Guibas, and Jorge Stolfi. “Optimal Point Location in a Monotone Subdivision.” SIAM Journal on Computing. SIAM, 1986. https://doi.org/10.1137/0215023.","ama":"Edelsbrunner H, Guibas L, Stolfi J. Optimal point location in a monotone subdivision. SIAM Journal on Computing. 1986;15(2):317-340. doi:10.1137/0215023"},"date_published":"1986-01-01T00:00:00Z","year":"1986","title":"Optimal point location in a monotone subdivision","month":"01","date_updated":"2022-02-01T10:05:55Z","quality_controlled":"1","day":"01","oa_version":"None","volume":15,"abstract":[{"text":"Point location, often known in graphics as “hit detection,” is one of the fundamental problems of computational geometry. In a point location query we want to identify which of a given collection of geometric objects contains a particular point. Let $\\mathcal{S}$ denote a subdivision of the Euclidean plane into monotone regions by a straight-line graph of $m$ edges. In this paper we exhibit a substantial refinement of the technique of Lee and Preparata [SIAM J. Comput., 6 (1977), pp. 594–606] for locating a point in $\\mathcal{S}$ based on separating chains. The new data structure, called a layered dag, can be built in $O(m)$ time, uses $O(m)$ storage, and makes possible point location in $O(\\log m)$ time. Unlike previous structures that attain these optimal bounds, the layered dag can be implemented in a simple and practical way, and is extensible to subdivisions with edges more general than straight-line segments.\r\n© 1986 Society for Industrial and Applied Mathematics","lang":"eng"}],"article_type":"original","_id":"4104","extern":"1","type":"journal_article","author":[{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","full_name":"Edelsbrunner, Herbert","last_name":"Edelsbrunner","first_name":"Herbert","orcid":"0000-0002-9823-6833"},{"first_name":"Leonidas","full_name":"Guibas, Leonidas","last_name":"Guibas"},{"first_name":"Jorge","last_name":"Stolfi","full_name":"Stolfi, Jorge"}],"acknowledgement":"We would like to thank Andrei Broder, Dan Greene, Mary Claire van Leunen, Greg Nelson, Lyle Ramshaw, and F. Frances Yao, whose comments and suggestions have greatly improved the readability of this paper.","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","issue":"2","language":[{"iso":"eng"}],"publication":"SIAM Journal on Computing","status":"public","scopus_import":"1","date_created":"2018-12-11T12:06:58Z","page":"317 - 340","intvolume":" 15","publist_id":"2016"}]