---
OA_place: publisher
OA_type: gold
_id: '22916'
abstract:
- lang: eng
  text: "In the imprecise geometry model, the input is a family of regions F = (R₁,
    R₂, …,R_n), each containing a point p_i ∈ R_i. The task is then to compute some
    function of the points p₁,p₂,… p_n, in our case an implicit representation of
    their Pareto front. To this end, one may query a region R_i to retrieve its contained
    point p_i ∈ R_i. In this model, efficiency is interpreted in two ways: minimizing
    (i) the number of retrievals, and (ii) the computation time both for preprocessing,
    and the execution of the query stage, i.e. for computing which points to query
    and constructing the output. \r\nWe present an algorithm to construct (an implicit
    representation of) the Pareto front for possibly overlapping rectangles, that
    is instance-optimal with respect to the number of retrievals. This means that
    for every fixed input (F, P), there is no algorithm that retrieves asymptotically
    fewer regions to compute the output. This is a strong algorithmic quality, as
    it means that our algorithm is competitive even to clairvoyant algorithms which
    only have to verify the correctness of a correct guess. In terms of algorithmic
    running time, instance-optimality is provably unobtainable. We instead present
    an algorithm which is within a log n-factor of instance optimality. This generalizes
    earlier results which assumed the regions to not overlap, at only a minor cost
    in running time. \r\nFor unit squares, we present an algorithm that is not only
    instance optimal in the number of retrievals, but also universally optimal in
    terms of running time. This means that for any fixed set of regions F, no algorithm
    has a better worst-case running time for all possible point sets P. Thus, this
    work presents the first universally optimal algorithm for overlapping planar input.
    Compared to previous work, our result improves the degree to which the input regions
    may overlap, the preprocessing time, the number of retrievals, and the running
    time."
acknowledgement: This work was supported by the the VILLUM Foundation grant (VIL37507)
  "Efficient Recomputations for Changeful Problems".
alternative_title:
- LIPIcs
article_number: '106'
article_processing_charge: Yes
arxiv: 1
author:
- first_name: Sarita
  full_name: De Berg, Sarita
  last_name: De Berg
- first_name: Nynne Maria Foldager
  full_name: Bække, Nynne Maria Foldager
  last_name: Bække
- first_name: Frida Astrup
  full_name: Eriksen, Frida Astrup
  last_name: Eriksen
- first_name: Ivor
  full_name: Van Der Hoog, Ivor
  last_name: Van Der Hoog
- first_name: Eva
  full_name: Rotenberg, Eva
  last_name: Rotenberg
- first_name: Daniel P
  full_name: Rutschmann, Daniel P
  id: 7397d908-b582-11f0-bf73-88b902e86527
  last_name: Rutschmann
citation:
  ama: 'De Berg S, Bække NMF, Eriksen FA, Van Der Hoog I, Rotenberg E, Rutschmann
    DP. Instance optimal and universally optimal bounds for imprecise pareto fronts.
    In: <i>34th Annual European Symposium on Algorithms</i>. Vol 388. Schloss Dagstuhl
    - Leibniz-Zentrum für Informatik; 2026. doi:<a href="https://doi.org/10.4230/LIPIcs.ESA.2026.106">10.4230/LIPIcs.ESA.2026.106</a>'
  apa: 'De Berg, S., Bække, N. M. F., Eriksen, F. A., Van Der Hoog, I., Rotenberg,
    E., &#38; Rutschmann, D. P. (2026). Instance optimal and universally optimal bounds
    for imprecise pareto fronts. In <i>34th Annual European Symposium on Algorithms</i>
    (Vol. 388). L’Aquila, Italy: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
    <a href="https://doi.org/10.4230/LIPIcs.ESA.2026.106">https://doi.org/10.4230/LIPIcs.ESA.2026.106</a>'
  chicago: De Berg, Sarita, Nynne Maria Foldager Bække, Frida Astrup Eriksen, Ivor
    Van Der Hoog, Eva Rotenberg, and Daniel P Rutschmann. “Instance Optimal and Universally
    Optimal Bounds for Imprecise Pareto Fronts.” In <i>34th Annual European Symposium
    on Algorithms</i>, Vol. 388. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
    2026. <a href="https://doi.org/10.4230/LIPIcs.ESA.2026.106">https://doi.org/10.4230/LIPIcs.ESA.2026.106</a>.
  ieee: S. De Berg, N. M. F. Bække, F. A. Eriksen, I. Van Der Hoog, E. Rotenberg,
    and D. P. Rutschmann, “Instance optimal and universally optimal bounds for imprecise
    pareto fronts,” in <i>34th Annual European Symposium on Algorithms</i>, L’Aquila,
    Italy, 2026, vol. 388.
  ista: 'De Berg S, Bække NMF, Eriksen FA, Van Der Hoog I, Rotenberg E, Rutschmann
    DP. 2026. Instance optimal and universally optimal bounds for imprecise pareto
    fronts. 34th Annual European Symposium on Algorithms. ESA: European Symposium
    on Algorithms, LIPIcs, vol. 388, 106.'
  mla: De Berg, Sarita, et al. “Instance Optimal and Universally Optimal Bounds for
    Imprecise Pareto Fronts.” <i>34th Annual European Symposium on Algorithms</i>,
    vol. 388, 106, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026, doi:<a
    href="https://doi.org/10.4230/LIPIcs.ESA.2026.106">10.4230/LIPIcs.ESA.2026.106</a>.
  short: S. De Berg, N.M.F. Bække, F.A. Eriksen, I. Van Der Hoog, E. Rotenberg, D.P.
    Rutschmann, in:, 34th Annual European Symposium on Algorithms, Schloss Dagstuhl
    - Leibniz-Zentrum für Informatik, 2026.
conference:
  end_date: 2026-09-04
  location: L’Aquila, Italy
  name: 'ESA: European Symposium on Algorithms'
  start_date: 2026-08-31
corr_author: '1'
das_tickbox: '0'
date_created: 2026-09-13T22:01:52Z
date_published: 2026-08-25T00:00:00Z
date_updated: 2026-09-16T08:59:49Z
day: '25'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPIcs.ESA.2026.106
external_id:
  arxiv:
  - '2605.07523'
file:
- access_level: open_access
  checksum: 75cfae9e9773be4b06f9aab66041f0f3
  content_type: application/pdf
  creator: dernst
  date_created: 2026-09-16T08:58:04Z
  date_updated: 2026-09-16T08:58:04Z
  file_id: '22935'
  file_name: 2026_LIPIcsESA_deBerg.pdf
  file_size: 1102214
  relation: main_file
  success: 1
file_date_updated: 2026-09-16T08:58:04Z
fulldoi: https://doi.org/10.4230/LIPIcs.ESA.2026.106
has_accepted_license: '1'
intvolume: '       388'
keyword:
- Pareto front
- imprecise geometry
- instance optimality
- universal optimality
- preprocessing model
- partial information
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
publication: 34th Annual European Symposium on Algorithms
publication_identifier:
  isbn:
  - '9783959774451'
  issn:
  - 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: no
title: Instance optimal and universally optimal bounds for imprecise pareto fronts
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 388
year: '2026'
...
---
OA_place: publisher
OA_type: gold
_id: '22915'
abstract:
- lang: eng
  text: "The element distinctness problem takes as input a list I of n values from
    a totally ordered universe, where pairwise comparisons between values are allowed,
    and the goal is to decide whether I contains any duplicates. It is a well-studied
    problem with a classical worst-case Ω(n log n) comparison-based lower bound by
    Fredman [TCS'76]. At first glance, this lower bound appears to rule out any algorithm
    more efficient than the naive approach of sorting I and comparing adjacent elements.
    However, upon closer inspection, the Ω(n log n) bound is overly pessimistic. For
    instance, if I contains n/2 identical elements, a median-finding algorithm will,
    regardless of the input order, find a duplicate in linear time. This raises a
    natural question: Are there comparison-based lower bounds for element distinctness
    that are sensitive to the amount of duplicates in the input instance?\r\nTo address
    this question, we derive instance-specific lower bounds. For any input instance
    I, we represent the combinatorial structure of the duplicates in I by an undirected
    graph G(I) that connects identical elements. Each such graph G is a union of cliques,
    and we study algorithms by their worst-case running time over all inputs I' with
    G(I') ≅ G. We establish an adversarial lower bound showing that, for any deterministic
    algorithm \U0001D49C, there exists a graph G and an algorithm \U0001D49C' that,
    for all inputs I with G(I) ≅ G, is a factor O(log log n) faster than \U0001D49C.
    Consequently, no deterministic algorithm can be o(log log n)-competitive for all
    graphs G. We complement this with an O(log log n)-competitive deterministic algorithm,
    thereby obtaining tight bounds for element distinctness that go beyond classical
    worst-case analysis. Subsequently, we study the related problem of set intersection.
    We show that no deterministic set intersection algorithm can be o(log n)-competitive,
    and provide an O(log n)-competitive deterministic algorithm. We find it interesting
    and surprising to discover tight O(log log n)-competitive bounds for element distinctness.
    Moreover, we find the separation between element distinctness and the set intersection
    problem unexpected."
acknowledgement: "Ivor van der Hoog, Eva Rotenberg, and Daniel Rutschmann thank the
  VILLUM Foundation\r\ngrant (VIL37507) “Efficient Recomputations for Changeful Problems”
  for supporting this work.\r\nDaniel Rutschmann is supported by the European Research
  Council (ERC) under the European\r\nUnion’s Horizon 2020 research and innovation
  programme (No. 101019564) "
alternative_title:
- LIPIcs
article_number: '101'
article_processing_charge: Yes
arxiv: 1
author:
- first_name: Ivor
  full_name: Van Der Hoog, Ivor
  last_name: Van Der Hoog
- first_name: Eva
  full_name: Rotenberg, Eva
  last_name: Rotenberg
- first_name: Daniel P
  full_name: Rutschmann, Daniel P
  id: 7397d908-b582-11f0-bf73-88b902e86527
  last_name: Rutschmann
citation:
  ama: 'Van Der Hoog I, Rotenberg E, Rutschmann DP. Tight Better-Than-Worst-Case bounds
    for element distinctness and set intersection. In: <i>34th Annual European Symposium
    on Algorithms</i>. Vol 388. Schloss Dagstuhl - Leibniz-Zentrum für Informatik;
    2026. doi:<a href="https://doi.org/10.4230/LIPIcs.ESA.2026.101">10.4230/LIPIcs.ESA.2026.101</a>'
  apa: 'Van Der Hoog, I., Rotenberg, E., &#38; Rutschmann, D. P. (2026). Tight Better-Than-Worst-Case
    bounds for element distinctness and set intersection. In <i>34th Annual European
    Symposium on Algorithms</i> (Vol. 388). L’Aquila, Italy: Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik. <a href="https://doi.org/10.4230/LIPIcs.ESA.2026.101">https://doi.org/10.4230/LIPIcs.ESA.2026.101</a>'
  chicago: Van Der Hoog, Ivor, Eva Rotenberg, and Daniel P Rutschmann. “Tight Better-Than-Worst-Case
    Bounds for Element Distinctness and Set Intersection.” In <i>34th Annual European
    Symposium on Algorithms</i>, Vol. 388. Schloss Dagstuhl - Leibniz-Zentrum für
    Informatik, 2026. <a href="https://doi.org/10.4230/LIPIcs.ESA.2026.101">https://doi.org/10.4230/LIPIcs.ESA.2026.101</a>.
  ieee: I. Van Der Hoog, E. Rotenberg, and D. P. Rutschmann, “Tight Better-Than-Worst-Case
    bounds for element distinctness and set intersection,” in <i>34th Annual European
    Symposium on Algorithms</i>, L’Aquila, Italy, 2026, vol. 388.
  ista: 'Van Der Hoog I, Rotenberg E, Rutschmann DP. 2026. Tight Better-Than-Worst-Case
    bounds for element distinctness and set intersection. 34th Annual European Symposium
    on Algorithms. ESA: European Symposium on Algorithms, LIPIcs, vol. 388, 101.'
  mla: Van Der Hoog, Ivor, et al. “Tight Better-Than-Worst-Case Bounds for Element
    Distinctness and Set Intersection.” <i>34th Annual European Symposium on Algorithms</i>,
    vol. 388, 101, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026, doi:<a
    href="https://doi.org/10.4230/LIPIcs.ESA.2026.101">10.4230/LIPIcs.ESA.2026.101</a>.
  short: I. Van Der Hoog, E. Rotenberg, D.P. Rutschmann, in:, 34th Annual European
    Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026.
conference:
  end_date: 2026-09-04
  location: L’Aquila, Italy
  name: 'ESA: European Symposium on Algorithms'
  start_date: 2026-08-31
corr_author: '1'
das_tickbox: '0'
date_created: 2026-09-13T22:01:52Z
date_published: 2026-08-25T00:00:00Z
date_updated: 2026-09-16T09:21:35Z
day: '25'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPIcs.ESA.2026.101
ec_funded: 1
external_id:
  arxiv:
  - '2511.02954'
file:
- access_level: open_access
  checksum: c552853bfa37e4b9a0f060107e464ed0
  content_type: application/pdf
  creator: dernst
  date_created: 2026-09-16T09:20:49Z
  date_updated: 2026-09-16T09:20:49Z
  file_id: '22937'
  file_name: 2026_LIPIcsESA_vanderHoog.pdf
  file_size: 892322
  relation: main_file
  success: 1
file_date_updated: 2026-09-16T09:20:49Z
fulldoi: https://doi.org/10.4230/LIPIcs.ESA.2026.101
has_accepted_license: '1'
intvolume: '       388'
keyword:
- Comparison-based analysis
- set intersection
- universal optimality
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
project:
- _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62
  call_identifier: H2020
  grant_number: '101019564'
  name: The design and evaluation of modern fully dynamic data structures
publication: 34th Annual European Symposium on Algorithms
publication_identifier:
  isbn:
  - '9783959774451'
  issn:
  - 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: yes
title: Tight Better-Than-Worst-Case bounds for element distinctness and set intersection
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 388
year: '2026'
...
---
OA_place: publisher
OA_type: gold
_id: '22917'
abstract:
- lang: eng
  text: 'A heap is a dynamic data structure that stores a set of labeled values under
    the following operations: pop returns the minimum value of the heap, Push(x_i)
    pushes a new value x_i onto the heap, and DecreaseKey(i, v) decreases the value
    x_i to v. A working-set heap is a heap that supports the x_i ← pop() operation
    in O(log Γ(x_i)) time where Γ(x_i) is the size of the working set: the number
    of elements that were pushed onto the heap while x_i was in the heap. The goal
    of working set heap design is to maintain the working set property while minimizing
    the overhead of the Push and DecreaseKey operations. On a word RAM, there exist
    working set heaps that support Push and DecreaseKey in amortized constant time.
    In this paper, we show via a simple construction that pointer machines, one of
    the most general and least-assuming computational models, support working set
    heaps that support Push in amortized constant time and DecreaseKey in inverse-Ackermann
    time. A by-product of this analysis is that Dijkstra’s shortest path algorithm
    can be near-universally optimal on a pointer machine - incurring only an additive
    O(m α(m)) overhead compared to the optimal running time for distance ordering,
    where m denotes the number of edges in the graph.'
acknowledgement: "Ivor van der Hoog, Eva Rotenberg, and Daniel Rutschmann thank the
  VILLUM Foundation\r\ngrant (VIL37507) “Efficient Recomputations for Changeful Problems”
  for supporting this work.\r\nDaniel Rutschmann is supported by the European Research
  Council (ERC) under the European\r\nUnion’s Horizon 2020 research and innovation
  programme (No. 101019564) . John Iacono\r\nis supported by the Fonds de la Recherche
  Scientifique – FNRS.This work started at Dagstuhl 25191: Adaptive and Scalable Data
  Structures.\r\n\r\n"
alternative_title:
- LIPIcs
article_number: 45:1-45:13
article_processing_charge: Yes
arxiv: 1
author:
- first_name: Ivor
  full_name: Van Der Hoog, Ivor
  last_name: Van Der Hoog
- first_name: John
  full_name: Iacono, John
  last_name: Iacono
- first_name: Eva
  full_name: Rotenberg, Eva
  last_name: Rotenberg
- first_name: Daniel P
  full_name: Rutschmann, Daniel P
  id: 7397d908-b582-11f0-bf73-88b902e86527
  last_name: Rutschmann
citation:
  ama: 'Van Der Hoog I, Iacono J, Rotenberg E, Rutschmann DP. Near-optimal working-set
    heaps and dijkstra on pointer machines. In: <i>34th Annual European Symposium
    on Algorithms</i>. Vol 388. Schloss Dagstuhl - Leibniz-Zentrum für Informatik;
    2026. doi:<a href="https://doi.org/10.4230/LIPIcs.ESA.2026.45">10.4230/LIPIcs.ESA.2026.45</a>'
  apa: 'Van Der Hoog, I., Iacono, J., Rotenberg, E., &#38; Rutschmann, D. P. (2026).
    Near-optimal working-set heaps and dijkstra on pointer machines. In <i>34th Annual
    European Symposium on Algorithms</i> (Vol. 388). L’Aquila, Italy: Schloss Dagstuhl
    - Leibniz-Zentrum für Informatik. <a href="https://doi.org/10.4230/LIPIcs.ESA.2026.45">https://doi.org/10.4230/LIPIcs.ESA.2026.45</a>'
  chicago: Van Der Hoog, Ivor, John Iacono, Eva Rotenberg, and Daniel P Rutschmann.
    “Near-Optimal Working-Set Heaps and Dijkstra on Pointer Machines.” In <i>34th
    Annual European Symposium on Algorithms</i>, Vol. 388. Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik, 2026. <a href="https://doi.org/10.4230/LIPIcs.ESA.2026.45">https://doi.org/10.4230/LIPIcs.ESA.2026.45</a>.
  ieee: I. Van Der Hoog, J. Iacono, E. Rotenberg, and D. P. Rutschmann, “Near-optimal
    working-set heaps and dijkstra on pointer machines,” in <i>34th Annual European
    Symposium on Algorithms</i>, L’Aquila, Italy, 2026, vol. 388.
  ista: 'Van Der Hoog I, Iacono J, Rotenberg E, Rutschmann DP. 2026. Near-optimal
    working-set heaps and dijkstra on pointer machines. 34th Annual European Symposium
    on Algorithms. ESA: European Symposium on Algorithms, LIPIcs, vol. 388, 45:1-45:13.'
  mla: Van Der Hoog, Ivor, et al. “Near-Optimal Working-Set Heaps and Dijkstra on
    Pointer Machines.” <i>34th Annual European Symposium on Algorithms</i>, vol. 388,
    45:1-45:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026, doi:<a href="https://doi.org/10.4230/LIPIcs.ESA.2026.45">10.4230/LIPIcs.ESA.2026.45</a>.
  short: I. Van Der Hoog, J. Iacono, E. Rotenberg, D.P. Rutschmann, in:, 34th Annual
    European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
    2026.
conference:
  end_date: 2026-09-04
  location: L’Aquila, Italy
  name: 'ESA: European Symposium on Algorithms'
  start_date: 2026-08-31
corr_author: '1'
das_tickbox: '0'
date_created: 2026-09-13T22:01:53Z
date_published: 2026-08-25T00:00:00Z
date_updated: 2026-09-17T10:35:56Z
day: '25'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPIcs.ESA.2026.45
ec_funded: 1
external_id:
  arxiv:
  - '2604.24134'
file:
- access_level: open_access
  checksum: 52e7cb8881060e8f17b89cd46504f445
  content_type: application/pdf
  creator: dernst
  date_created: 2026-09-17T10:33:12Z
  date_updated: 2026-09-17T10:33:12Z
  file_id: '22949'
  file_name: 2026_LIPIcsESA_vanderHoog2.pdf
  file_size: 792024
  relation: main_file
  success: 1
file_date_updated: 2026-09-17T10:33:12Z
fulldoi: https://doi.org/10.4230/LIPIcs.ESA.2026.45
has_accepted_license: '1'
intvolume: '       388'
keyword:
- Data structures
- graph algorithms
- amortized analysis
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
project:
- _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62
  call_identifier: H2020
  grant_number: '101019564'
  name: The design and evaluation of modern fully dynamic data structures
publication: 34th Annual European Symposium on Algorithms
publication_identifier:
  eissn:
  - 1868-8969
  isbn:
  - '9783959774451'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: no
title: Near-optimal working-set heaps and dijkstra on pointer machines
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 388
year: '2026'
...