DROPS

Document

DOI: 10.4230/LIPIcs.WADS.2025.21

A WSPD, Separator and Small Tree Cover for c-Packed Graphs

Authors: Lindsey Deryckere, Joachim Gudmundsson, André van Renssen, Yuan Sha, and Sampson Wong

Published in: LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025)

Abstract

The c-packedness property, proposed in 2010, is a geometric property that captures the spatial distribution of a set of edges. Despite the recent interest in c-packedness, its utility has so far been limited to Fréchet distance problems. An open problem is whether a wider variety of algorithmic and data structure problems can be solved efficiently under the c-packedness assumption, and more specifically, on c-packed graphs. In this paper, we prove two fundamental properties of c-packed graphs: that there exists a linear-size well-separated pair decomposition under the graph metric, and there exists a constant size balanced separator. We then apply these fundamental properties to obtain a small tree cover for the metric space and distance oracles under the shortest path metric. In particular, we obtain a tree cover of constant size, an exact distance oracle of near-linear size and an approximate distance oracle of linear size.

Cite as

Lindsey Deryckere, Joachim Gudmundsson, André van Renssen, Yuan Sha, and Sampson Wong. A WSPD, Separator and Small Tree Cover for c-Packed Graphs. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 21:1-21:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{deryckere_et_al:LIPIcs.WADS.2025.21,
  author =	{Deryckere, Lindsey and Gudmundsson, Joachim and van Renssen, Andr\'{e} and Sha, Yuan and Wong, Sampson},
  title =	{{A WSPD, Separator and Small Tree Cover for c-Packed Graphs}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{21:1--21:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.21},
  URN =		{urn:nbn:de:0030-drops-242529},
  doi =		{10.4230/LIPIcs.WADS.2025.21},
  annote =	{Keywords: Well-separated pair decomposition, separator, tree cover, distance oracles, realistic graphs}
}

Document

APPROX

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.17

Online Matching with Set and Concave Delays

Authors: Lindsey Deryckere and Seeun William Umboh

Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)

Abstract

We initiate the study of online problems with set delay, where the delay cost at any given time is an arbitrary function of the set of pending requests. In particular, we study the online min-cost perfect matching with set delay (MPMD-Set) problem, which generalises the online min-cost perfect matching with delay (MPMD) problem introduced by Emek et al. (STOC 2016). In MPMD, m requests arrive over time in a metric space of n points. When a request arrives the algorithm must choose to either match or delay the request. The goal is to create a perfect matching of all requests while minimising the sum of distances between matched requests, and the total delay costs incurred by each of the requests. In contrast to previous work we study MPMD-Set in the non-clairvoyant setting, where the algorithm does not know the future delay costs. We first show no algorithm is competitive in n or m. We then study the natural special case of size-based delay where the delay is a non-decreasing function of the number of unmatched requests. Our main result is the first non-clairvoyant algorithms for online min-cost perfect matching with size-based delay that are competitive in terms of m. In fact, these are the first non-clairvoyant algorithms for any variant of MPMD. A key technical ingredient is an analog of the symmetric difference of matchings that may be useful for other special classes of set delay. Furthermore, we prove a lower bound of Ω(n) for any deterministic algorithm and Ω(log n) for any randomised algorithm. These lower bounds also hold for clairvoyant algorithms. Finally, we also give an m-competitive deterministic algorithm for uniform concave delays in the clairvoyant setting.

Cite as

Lindsey Deryckere and Seeun William Umboh. Online Matching with Set and Concave Delays. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 17:1-17:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{deryckere_et_al:LIPIcs.APPROX/RANDOM.2023.17,
  author =	{Deryckere, Lindsey and Umboh, Seeun William},
  title =	{{Online Matching with Set and Concave Delays}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{17:1--17:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-296-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{275},
  editor =	{Megow, Nicole and Smith, Adam},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.17},
  URN =		{urn:nbn:de:0030-drops-188423},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.17},
  annote =	{Keywords: online algorithms, matching, delay, non-clairvoyant}
}

Search Results

Documents authored by Deryckere, Lindsey

A WSPD, Separator and Small Tree Cover for c-Packed Graphs

Abstract

Cite as

Online Matching with Set and Concave Delays

Abstract

Cite as

Thanks for your feedback!

Could not send message