---
_id: '8703'
abstract:
- lang: eng
  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. '
alternative_title:
- LIPIcs
article_number: '75'
article_processing_charge: No
author:
- first_name: Georg F
  full_name: Osang, Georg F
  id: 464B40D6-F248-11E8-B48F-1D18A9856A87
  last_name: Osang
  orcid: 0000-0002-8882-5116
- first_name: Mael
  full_name: Rouxel-Labbé, Mael
  last_name: Rouxel-Labbé
- first_name: Monique
  full_name: Teillaud, Monique
  last_name: Teillaud
citation:
  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>'
  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>'
  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>.
  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.
  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.'
  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>.
  short: G.F. Osang, M. Rouxel-Labbé, M. Teillaud, in:, 28th Annual European Symposium
    on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
conference:
  end_date: 2020-09-09
  location: Virtual, Online; Pisa, Italy
  name: 'ESA: Annual European Symposium on Algorithms'
  start_date: 2020-09-07
date_created: 2020-10-25T23:01:18Z
date_published: 2020-08-26T00:00:00Z
date_updated: 2023-09-07T13:29:00Z
day: '26'
ddc:
- '000'
department:
- _id: HeEd
doi: 10.4230/LIPIcs.ESA.2020.75
ec_funded: 1
file:
- access_level: open_access
  checksum: fe0f7c49a99ed870c671b911e10d5496
  content_type: application/pdf
  creator: cziletti
  date_created: 2020-10-27T14:31:52Z
  date_updated: 2020-10-27T14:31:52Z
  file_id: '8712'
  file_name: 2020_LIPIcs_Osang.pdf
  file_size: 733291
  relation: main_file
  success: 1
file_date_updated: 2020-10-27T14:31:52Z
has_accepted_license: '1'
intvolume: '       173'
language:
- iso: eng
license: https://creativecommons.org/licenses/by/3.0/
month: '08'
oa: 1
oa_version: Published Version
project:
- _id: 266A2E9E-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '788183'
  name: Alpha Shape Theory Extended
publication: 28th Annual European Symposium on Algorithms
publication_identifier:
  isbn:
  - '9783959771627'
  issn:
  - '18688969'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
related_material:
  record:
  - id: '9056'
    relation: dissertation_contains
    status: public
scopus_import: '1'
status: public
title: Generalizing CGAL periodic Delaunay triangulations
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/3.0/legalcode
  name: Creative Commons Attribution 3.0 Unported (CC BY 3.0)
  short: CC BY (3.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 173
year: '2020'
...
---
_id: '11816'
abstract:
- lang: eng
  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.
alternative_title:
- LIPIcs
article_number: '58'
article_processing_charge: No
arxiv: 1
author:
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: Khan
  full_name: Shahbaz, Khan
  last_name: Shahbaz
- first_name: Richard
  full_name: Paul, Richard
  last_name: Paul
- first_name: Christian
  full_name: Schulz, Christian
  last_name: Schulz
citation:
  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>'
  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>'
  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>.
  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.
  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.'
  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>.
  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.
conference:
  end_date: 2020-09-09
  location: Pisa, Italy
  name: 'ESA: Annual European Symposium on Algorithms'
  start_date: 2020-09-07
date_created: 2022-08-12T07:13:25Z
date_published: 2020-08-26T00:00:00Z
date_updated: 2023-02-14T08:57:55Z
day: '26'
doi: 10.4230/LIPIcs.ESA.2020.58
extern: '1'
external_id:
  arxiv:
  - '2004.09099'
intvolume: '       173'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.4230/LIPIcs.ESA.2020.58
month: '08'
oa: 1
oa_version: Published Version
publication: 8th Annual European Symposium on Algorithms
publication_identifier:
  isbn:
  - '9783959771627'
  issn:
  - 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Dynamic matching algorithms in practice
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 173
year: '2020'
...
---
_id: '11818'
abstract:
- lang: eng
  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."
alternative_title:
- LIPIcs
article_number: '57'
article_processing_charge: No
arxiv: 1
author:
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: Sagar
  full_name: Kale, Sagar
  last_name: Kale
citation:
  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>'
  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>'
  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>.
  ieee: M. H. Henzinger and S. Kale, “Fully-dynamic coresets,” in <i>28th Annual European
    Symposium on Algorithms</i>, Pisa, Italy, 2020, vol. 173.
  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.'
  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>.
  short: M.H. Henzinger, S. Kale, in:, 28th Annual European Symposium on Algorithms,
    Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
conference:
  end_date: 2020-09-09
  location: Pisa, Italy
  name: 'ESA: Annual European Symposium on Algorithms'
  start_date: 2020-09-07
date_created: 2022-08-12T07:22:55Z
date_published: 2020-08-26T00:00:00Z
date_updated: 2023-02-14T09:29:51Z
day: '26'
doi: 10.4230/LIPIcs.ESA.2020.57
extern: '1'
external_id:
  arxiv:
  - '2004.14891'
intvolume: '       173'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.4230/LIPIcs.ESA.2020.57
month: '08'
oa: 1
oa_version: Published Version
publication: 28th Annual European Symposium on Algorithms
publication_identifier:
  isbn:
  - '9783959771627'
  issn:
  - 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Fully-dynamic coresets
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 173
year: '2020'
...
---
_id: '11819'
abstract:
- lang: eng
  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.
alternative_title:
- LIPIcs
article_number: '59'
article_processing_charge: No
arxiv: 1
author:
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: Alexander
  full_name: Noe, Alexander
  last_name: Noe
- first_name: Christian
  full_name: Schulz, Christian
  last_name: Schulz
- first_name: Darren
  full_name: Strash, Darren
  last_name: Strash
citation:
  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>'
  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>'
  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.
  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.'
  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>.
  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.
conference:
  end_date: 2020-09-09
  location: Pisa, Italy
  name: 'ESA: Annual European Symposium on Algorithms'
  start_date: 2020-09-07
date_created: 2022-08-12T07:27:42Z
date_published: 2020-08-26T00:00:00Z
date_updated: 2023-02-14T09:39:18Z
day: '26'
doi: 10.4230/LIPIcs.ESA.2020.59
extern: '1'
external_id:
  arxiv:
  - '2002.06948'
intvolume: '       173'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.4230/LIPIcs.ESA.2020.59
month: '08'
oa: 1
oa_version: Published Version
publication: 28th Annual European Symposium on Algorithms
publication_identifier:
  isbn:
  - '9783959771627'
  issn:
  - 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Finding all global minimum cuts in practice
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 173
year: '2020'
...