[{"ec_funded":1,"date_published":"2020-08-26T00:00:00Z","conference":{"start_date":"2020-09-07","end_date":"2020-09-09","name":"ESA: Annual European Symposium on Algorithms","location":"Virtual, Online; Pisa, Italy"},"publication":"28th Annual European Symposium on Algorithms","status":"public","project":[{"_id":"266A2E9E-B435-11E9-9278-68D0E5697425","name":"Alpha Shape Theory Extended","grant_number":"788183","call_identifier":"H2020"}],"year":"2020","related_material":{"record":[{"relation":"dissertation_contains","status":"public","id":"9056"}]},"quality_controlled":"1","ddc":["000"],"_id":"8703","date_updated":"2023-09-07T13:29:00Z","type":"conference","article_processing_charge":"No","alternative_title":["LIPIcs"],"doi":"10.4230/LIPIcs.ESA.2020.75","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","citation":{"short":"G.F. Osang, M. Rouxel-Labbé, M. Teillaud, in:, 28th Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.","ieee":"G. F. Osang, M. Rouxel-Labbé, and M. Teillaud, “Generalizing CGAL periodic Delaunay triangulations,” in <i>28th Annual European Symposium on Algorithms</i>, Virtual, Online; Pisa, Italy, 2020, vol. 173.","ama":"Osang GF, Rouxel-Labbé M, Teillaud M. Generalizing CGAL periodic Delaunay triangulations. In: <i>28th Annual European Symposium on Algorithms</i>. Vol 173. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2020.75\">10.4230/LIPIcs.ESA.2020.75</a>","mla":"Osang, Georg F., et al. “Generalizing CGAL Periodic Delaunay Triangulations.” <i>28th Annual European Symposium on Algorithms</i>, vol. 173, 75, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2020.75\">10.4230/LIPIcs.ESA.2020.75</a>.","apa":"Osang, G. F., Rouxel-Labbé, M., &#38; Teillaud, M. (2020). Generalizing CGAL periodic Delaunay triangulations. In <i>28th Annual European Symposium on Algorithms</i> (Vol. 173). Virtual, Online; Pisa, Italy: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2020.75\">https://doi.org/10.4230/LIPIcs.ESA.2020.75</a>","ista":"Osang GF, Rouxel-Labbé M, Teillaud M. 2020. Generalizing CGAL periodic Delaunay triangulations. 28th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 173, 75.","chicago":"Osang, Georg F, Mael Rouxel-Labbé, and Monique Teillaud. “Generalizing CGAL Periodic Delaunay Triangulations.” In <i>28th Annual European Symposium on Algorithms</i>, Vol. 173. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2020.75\">https://doi.org/10.4230/LIPIcs.ESA.2020.75</a>."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa":1,"language":[{"iso":"eng"}],"department":[{"_id":"HeEd"}],"article_number":"75","file":[{"date_updated":"2020-10-27T14:31:52Z","creator":"cziletti","file_size":733291,"date_created":"2020-10-27T14:31:52Z","file_id":"8712","access_level":"open_access","content_type":"application/pdf","success":1,"file_name":"2020_LIPIcs_Osang.pdf","checksum":"fe0f7c49a99ed870c671b911e10d5496","relation":"main_file"}],"month":"08","file_date_updated":"2020-10-27T14:31:52Z","publication_identifier":{"issn":["18688969"],"isbn":["9783959771627"]},"publication_status":"published","has_accepted_license":"1","intvolume":"       173","license":"https://creativecommons.org/licenses/by/3.0/","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/3.0/legalcode","name":"Creative Commons Attribution 3.0 Unported (CC BY 3.0)","image":"/images/cc_by.png","short":"CC BY (3.0)"},"abstract":[{"text":"Even though Delaunay originally introduced his famous triangulations in the case of infinite point sets with translational periodicity, a software that computes such triangulations in the general case is not yet available, to the best of our knowledge. Combining and generalizing previous work, we present a practical algorithm for computing such triangulations. The algorithm has been implemented and experiments show that its performance is as good as the one of the CGAL package, which is restricted to cubic periodicity. ","lang":"eng"}],"volume":173,"date_created":"2020-10-25T23:01:18Z","scopus_import":"1","day":"26","author":[{"last_name":"Osang","full_name":"Osang, Georg F","id":"464B40D6-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-8882-5116","first_name":"Georg F"},{"full_name":"Rouxel-Labbé, Mael","last_name":"Rouxel-Labbé","first_name":"Mael"},{"last_name":"Teillaud","full_name":"Teillaud, Monique","first_name":"Monique"}],"title":"Generalizing CGAL periodic Delaunay triangulations","oa_version":"Published Version"},{"publication_identifier":{"issn":["1868-8969"],"isbn":["9783959771627"]},"publication_status":"published","intvolume":"       173","abstract":[{"text":"In recent years, significant advances have been made in the design and analysis of fully dynamic maximal matching algorithms. However, these theoretical results have received very little attention from the practical perspective. Few of the algorithms are implemented and tested on real datasets, and their practical potential is far from understood. In this paper, we attempt to bridge the gap between theory and practice that is currently observed for the fully dynamic maximal matching problem. We engineer several algorithms and empirically study those algorithms on an extensive set of dynamic instances.","lang":"eng"}],"date_created":"2022-08-12T07:13:25Z","volume":173,"oa_version":"Published Version","title":"Dynamic matching algorithms in practice","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":"Khan","full_name":"Shahbaz, Khan","last_name":"Shahbaz"},{"full_name":"Paul, Richard","last_name":"Paul","first_name":"Richard"},{"first_name":"Christian","last_name":"Schulz","full_name":"Schulz, Christian"}],"day":"26","scopus_import":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"ista":"Henzinger MH, Shahbaz K, Paul R, Schulz C. 2020. Dynamic matching algorithms in practice. 8th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 173, 58.","chicago":"Henzinger, Monika H, Khan Shahbaz, Richard Paul, and Christian Schulz. “Dynamic Matching Algorithms in Practice.” In <i>8th Annual European Symposium on Algorithms</i>, Vol. 173. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2020.58\">https://doi.org/10.4230/LIPIcs.ESA.2020.58</a>.","mla":"Henzinger, Monika H., et al. “Dynamic Matching Algorithms in Practice.” <i>8th Annual European Symposium on Algorithms</i>, vol. 173, 58, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2020.58\">10.4230/LIPIcs.ESA.2020.58</a>.","apa":"Henzinger, M. H., Shahbaz, K., Paul, R., &#38; Schulz, C. (2020). Dynamic matching algorithms in practice. In <i>8th Annual European Symposium on Algorithms</i> (Vol. 173). Pisa, Italy: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2020.58\">https://doi.org/10.4230/LIPIcs.ESA.2020.58</a>","ama":"Henzinger MH, Shahbaz K, Paul R, Schulz C. Dynamic matching algorithms in practice. In: <i>8th Annual European Symposium on Algorithms</i>. Vol 173. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2020.58\">10.4230/LIPIcs.ESA.2020.58</a>","short":"M.H. Henzinger, K. Shahbaz, R. Paul, C. Schulz, in:, 8th Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.","ieee":"M. H. Henzinger, K. Shahbaz, R. Paul, and C. Schulz, “Dynamic matching algorithms in practice,” in <i>8th Annual European Symposium on Algorithms</i>, Pisa, Italy, 2020, vol. 173."},"language":[{"iso":"eng"}],"oa":1,"article_number":"58","arxiv":1,"month":"08","quality_controlled":"1","main_file_link":[{"url":"https://doi.org/10.4230/LIPIcs.ESA.2020.58","open_access":"1"}],"type":"conference","date_updated":"2023-02-14T08:57:55Z","_id":"11816","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","doi":"10.4230/LIPIcs.ESA.2020.58","article_processing_charge":"No","alternative_title":["LIPIcs"],"conference":{"start_date":"2020-09-07","end_date":"2020-09-09","name":"ESA: Annual European Symposium on Algorithms","location":"Pisa, Italy"},"date_published":"2020-08-26T00:00:00Z","extern":"1","status":"public","publication":"8th Annual European Symposium on Algorithms","external_id":{"arxiv":["2004.09099"]},"year":"2020"},{"volume":173,"date_created":"2022-08-12T07:22:55Z","author":[{"orcid":"0000-0002-5008-6530","first_name":"Monika H","full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger"},{"last_name":"Kale","full_name":"Kale, Sagar","first_name":"Sagar"}],"day":"26","scopus_import":"1","oa_version":"Published Version","title":"Fully-dynamic coresets","publication_status":"published","publication_identifier":{"isbn":["9783959771627"],"issn":["1868-8969"]},"abstract":[{"text":"With input sizes becoming massive, coresets - small yet representative summary of the input - are relevant more than ever. A weighted set C_w that is a subset of the input is an ε-coreset if the cost of any feasible solution S with respect to C_w is within [1±ε] of the cost of S with respect to the original input. We give a very general technique to compute coresets in the fully-dynamic setting where input points can be added or deleted. Given a static (i.e., not dynamic) ε-coreset-construction algorithm that runs in time t(n, ε, λ) and computes a coreset of size s(n, ε, λ), where n is the number of input points and 1-λ is the success probability, we give a fully-dynamic algorithm that computes an ε-coreset with worst-case update time O((log n) ⋅ t(s(n, ε/log n, λ/n), ε/log n, λ/n)) (this bound is stated informally), where the success probability is 1-λ. Our technique is a fully-dynamic analog of the merge-and-reduce technique, which is due to Har-Peled and Mazumdar [Har-Peled and Mazumdar, 2004] and is based on a technique of Bentley and Saxe [Jon Louis Bentley and James B. Saxe, 1980], that applies to the insertion-only setting where points can only be added. Although, our space usage is O(n), our technique works in the presence of an adaptive adversary, and we show that Ω(n) space is required when adversary is adaptive.\r\nAs a concrete implication of our technique, using the result of Braverman et al. [{Braverman} et al., 2016], we get fully-dynamic ε-coreset-construction algorithms for k-median and k-means with worst-case update time O(ε^{-2} k² log⁵ n log³ k) and coreset size O(ε^{-2} k log n log² k) ignoring log log n and log(1/ε) factors and assuming that ε = Ω(1/poly(n)) and λ = Ω(1/poly(n)) (which are very weak assumptions made only to make these bounds easy to parse). This results in the first fully-dynamic constant-approximation algorithms for k-median and k-means with update times O(poly(k, log n, ε^{-1})). Specifically, the dependence on k is only quadratic, and the bounds are worst-case. The best previous bound for both problems was amortized O(nlog n) by Cohen-Addad et al. [Cohen-Addad et al., 2019] via randomized O(1)-coresets in O(n) space.\r\nWe also show that under the OMv conjecture [Monika Henzinger et al., 2015], a fully-dynamic (4 - δ)-approximation algorithm for k-means must either have an amortized update time of Ω(k^{1-γ}) or amortized query time of Ω(k^{2 - γ}), where γ > 0 is a constant.","lang":"eng"}],"intvolume":"       173","article_number":"57","arxiv":1,"month":"08","citation":{"apa":"Henzinger, M. H., &#38; Kale, S. (2020). Fully-dynamic coresets. In <i>28th Annual European Symposium on Algorithms</i> (Vol. 173). Pisa, Italy: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2020.57\">https://doi.org/10.4230/LIPIcs.ESA.2020.57</a>","mla":"Henzinger, Monika H., and Sagar Kale. “Fully-Dynamic Coresets.” <i>28th Annual European Symposium on Algorithms</i>, vol. 173, 57, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2020.57\">10.4230/LIPIcs.ESA.2020.57</a>.","chicago":"Henzinger, Monika H, and Sagar Kale. “Fully-Dynamic Coresets.” In <i>28th Annual European Symposium on Algorithms</i>, Vol. 173. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2020.57\">https://doi.org/10.4230/LIPIcs.ESA.2020.57</a>.","ista":"Henzinger MH, Kale S. 2020. Fully-dynamic coresets. 28th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 173, 57.","ieee":"M. H. Henzinger and S. Kale, “Fully-dynamic coresets,” in <i>28th Annual European Symposium on Algorithms</i>, Pisa, Italy, 2020, vol. 173.","short":"M.H. Henzinger, S. Kale, in:, 28th Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.","ama":"Henzinger MH, Kale S. Fully-dynamic coresets. In: <i>28th Annual European Symposium on Algorithms</i>. Vol 173. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2020.57\">10.4230/LIPIcs.ESA.2020.57</a>"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa":1,"language":[{"iso":"eng"}],"date_updated":"2023-02-14T09:29:51Z","_id":"11818","type":"conference","doi":"10.4230/LIPIcs.ESA.2020.57","article_processing_charge":"No","alternative_title":["LIPIcs"],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","main_file_link":[{"url":"https://doi.org/10.4230/LIPIcs.ESA.2020.57","open_access":"1"}],"quality_controlled":"1","year":"2020","external_id":{"arxiv":["2004.14891"]},"date_published":"2020-08-26T00:00:00Z","conference":{"location":"Pisa, Italy","end_date":"2020-09-09","start_date":"2020-09-07","name":"ESA: Annual European Symposium on Algorithms"},"extern":"1","status":"public","publication":"28th Annual European Symposium on Algorithms"},{"year":"2020","external_id":{"arxiv":["2002.06948"]},"date_published":"2020-08-26T00:00:00Z","conference":{"location":"Pisa, Italy","start_date":"2020-09-07","end_date":"2020-09-09","name":"ESA: Annual European Symposium on Algorithms"},"publication":"28th Annual European Symposium on Algorithms","extern":"1","status":"public","date_updated":"2023-02-14T09:39:18Z","_id":"11819","type":"conference","doi":"10.4230/LIPIcs.ESA.2020.59","article_processing_charge":"No","alternative_title":["LIPIcs"],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","main_file_link":[{"open_access":"1","url":"https://doi.org/10.4230/LIPIcs.ESA.2020.59"}],"quality_controlled":"1","article_number":"59","arxiv":1,"month":"08","citation":{"apa":"Henzinger, M. H., Noe, A., Schulz, C., &#38; Strash, D. (2020). Finding all global minimum cuts in practice. In <i>28th Annual European Symposium on Algorithms</i> (Vol. 173). Pisa, Italy: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2020.59\">https://doi.org/10.4230/LIPIcs.ESA.2020.59</a>","mla":"Henzinger, Monika H., et al. “Finding All Global Minimum Cuts in Practice.” <i>28th Annual European Symposium on Algorithms</i>, vol. 173, 59, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2020.59\">10.4230/LIPIcs.ESA.2020.59</a>.","ista":"Henzinger MH, Noe A, Schulz C, Strash D. 2020. Finding all global minimum cuts in practice. 28th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 173, 59.","chicago":"Henzinger, Monika H, Alexander Noe, Christian Schulz, and Darren Strash. “Finding All Global Minimum Cuts in Practice.” In <i>28th Annual European Symposium on Algorithms</i>, Vol. 173. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2020.59\">https://doi.org/10.4230/LIPIcs.ESA.2020.59</a>.","ieee":"M. H. Henzinger, A. Noe, C. Schulz, and D. Strash, “Finding all global minimum cuts in practice,” in <i>28th Annual European Symposium on Algorithms</i>, Pisa, Italy, 2020, vol. 173.","short":"M.H. Henzinger, A. Noe, C. Schulz, D. Strash, in:, 28th Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.","ama":"Henzinger MH, Noe A, Schulz C, Strash D. Finding all global minimum cuts in practice. In: <i>28th Annual European Symposium on Algorithms</i>. Vol 173. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2020.59\">10.4230/LIPIcs.ESA.2020.59</a>"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa":1,"language":[{"iso":"eng"}],"volume":173,"date_created":"2022-08-12T07:27:42Z","author":[{"last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H","first_name":"Monika H","orcid":"0000-0002-5008-6530"},{"full_name":"Noe, Alexander","last_name":"Noe","first_name":"Alexander"},{"first_name":"Christian","last_name":"Schulz","full_name":"Schulz, Christian"},{"first_name":"Darren","full_name":"Strash, Darren","last_name":"Strash"}],"day":"26","scopus_import":"1","oa_version":"Published Version","title":"Finding all global minimum cuts in practice","publication_identifier":{"isbn":["9783959771627"],"issn":["1868-8969"]},"publication_status":"published","abstract":[{"text":"We present a practically efficient algorithm that finds all global minimum cuts in huge undirected graphs. Our algorithm uses a multitude of kernelization rules to reduce the graph to a small equivalent instance and then finds all minimum cuts using an optimized version of the algorithm of Nagamochi, Nakao and Ibaraki. In shared memory we are able to find all minimum cuts of graphs with up to billions of edges and millions of minimum cuts in a few minutes. We also give a new linear time algorithm to find the most balanced minimum cuts given as input the representation of all minimum cuts.","lang":"eng"}],"intvolume":"       173"}]