136 Search Results for "Daniel, Rolf"

Document
DOI: 10.4230/LIPIcs.SEA.2026.4
Integer Programming Models for the Median of a 0-1 String Set Under Levenshtein Distance

Authors: Claudio Arbib, Andrea D'Ascenzo, Oya E. Karaşan, and Andrea Pizzuti

Published in: LIPIcs, Volume 371, 24th International Symposium on Experimental Algorithms (SEA 2026)

Abstract
The Median String Problem calls for finding a string that minimizes the average distance from a given set of strings. Under the Levenshtein (or edit) metric, the problem is NP-hard even for binary strings. We devised two novel integer linear programming models for this case and tested them against the only formulation we are aware of in the literature. Our numerical experiments attest to the efficacy of the proposed approach.
Cite as

Claudio Arbib, Andrea D'Ascenzo, Oya E. Karaşan, and Andrea Pizzuti. Integer Programming Models for the Median of a 0-1 String Set Under Levenshtein Distance. In 24th International Symposium on Experimental Algorithms (SEA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 371, pp. 4:1-4:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{arbib_et_al:LIPIcs.SEA.2026.4,
  author =	{Arbib, Claudio and D'Ascenzo, Andrea and Kara\c{s}an, Oya E. and Pizzuti, Andrea},
  title =	{{Integer Programming Models for the Median of a 0-1 String Set Under Levenshtein Distance}},
  booktitle =	{24th International Symposium on Experimental Algorithms (SEA 2026)},
  pages =	{4:1--4:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-422-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{371},
  editor =	{Aum\"{u}ller, Martin and Finocchi, Irene},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2026.4},
  URN =		{urn:nbn:de:0030-drops-260081},
  doi =		{10.4230/LIPIcs.SEA.2026.4},
  annote =	{Keywords: Levenshtein Distance, Median String Problem, Integer Programming}
}
Document
DOI: 10.4230/LIPIcs.SEA.2026.8
General Multiplicative Spanners in Practice

Authors: Fritz Bökler, Markus Chimani, and Henning Jasper

Published in: LIPIcs, Volume 371, 24th International Symposium on Experimental Algorithms (SEA 2026)

Abstract
Given an undirected graph G with edge weights and lengths, a minimum α-spanner is a least-weight subgraph H ⊆ G that preserves distances w.r.t. the lengths between all node pairs up to a factor of α. Literature often takes the simplifying assumption of a single (coupled) edge function for weights and lengths. For such instances, several exact and non-exact algorithms are known and have been thoroughly evaluated in practice. However, many practical instances have decoupled form, as their weights and lengths are generally independent. Due to the increased complexity, only few (and even fewer practical) algorithms are able to guarantee low-weight solutions. This prompts practitioners to force their naturally decoupled instances into a coupled format, forsaking any quality guarantee. We implement several exact, approximative and heuristic algorithms for decoupled α-spanners, and use algorithm engineering to speed them up in practice. Our hypothesis-driven experiments evaluate their performance w.r.t. solution quality and speed. Generally, many practical instances can indeed be solved exactly within reasonable time, while LP-based approximation algorithms are not worthwhile. We find that standard greedy algorithms often yield acceptable results, but there are also practical instances for which they yield arbitrarily poor solutions. Here, augmented greedy variations offer a good compromise between solution quality and speed.
Cite as

Fritz Bökler, Markus Chimani, and Henning Jasper. General Multiplicative Spanners in Practice. In 24th International Symposium on Experimental Algorithms (SEA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 371, pp. 8:1-8:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bokler_et_al:LIPIcs.SEA.2026.8,
  author =	{B\"{o}kler, Fritz and Chimani, Markus and Jasper, Henning},
  title =	{{General Multiplicative Spanners in Practice}},
  booktitle =	{24th International Symposium on Experimental Algorithms (SEA 2026)},
  pages =	{8:1--8:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-422-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{371},
  editor =	{Aum\"{u}ller, Martin and Finocchi, Irene},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2026.8},
  URN =		{urn:nbn:de:0030-drops-260120},
  doi =		{10.4230/LIPIcs.SEA.2026.8},
  annote =	{Keywords: Graph spanners, ILP, experimental study, algorithm engineering}
}
Document
DOI: 10.4230/LIPIcs.SEA.2026.16
Efficient Large-Scale Text Precompression via Approximate LZ77 Parsings

Authors: Patrick Dinklage

Published in: LIPIcs, Volume 371, 24th International Symposium on Experimental Algorithms (SEA 2026)

Abstract
The LZ77 [Lempel and Ziv, 1977] compression scheme is ubiquitous: it lies at the core of everyday general-purpose standard compressors such as gzip or zstd, but also behind the scenes of many applications such as the compression of payloads transmitted in networks. Computing the exact LZ77 parsing is largely solved in theory: it can be done in sublinear time and space, in compressed space and in external memory, to name but some scenarios. However, these approaches are often impractical for everyday use due to their intensive time or space requirements. Standard compressors tackle this issue by introducing heuristics that go hand in hand with sophisticated encoding schemes to achieve very good compression fast and in small space, however, they only have a local view (e.g., a sliding window) on the input, potentially missing out on long-range repetitions that may be located far apart from one another. In this work, we design and implement - in C++ and leveraging shared-memory parallelism - compression pipelines that first precompress the input using an approximate LZ77 parsing taking care of long-range repetitions. This then serves as an assist to standard compressors for producing a succinct encoding of the remaining short and local repetitions. Similar approaches have been considered by [Kosolobov et al., 2020] and [Nalbach, 2024], respectively using Relative Lempel Ziv [Kuruppu et al. 2010] or the string synchronizing set [Kempa & Kociumaka, 2019]. We fill a gap taking the route via the prefix-free parsing [Boucher et al., 2019], using an intermediate result of [Hong et al., 2023]. On large repetitive inputs of tens of gigabytes, our pipelines are orders of magnitudes faster than the state of the art for computing the exact LZ77 parsing, use space less than the input size and still - despite producing more phrases - achieve the best overall compression in comparison to related work.
Cite as

Patrick Dinklage. Efficient Large-Scale Text Precompression via Approximate LZ77 Parsings. In 24th International Symposium on Experimental Algorithms (SEA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 371, pp. 16:1-16:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{dinklage:LIPIcs.SEA.2026.16,
  author =	{Dinklage, Patrick},
  title =	{{Efficient Large-Scale Text Precompression via Approximate LZ77 Parsings}},
  booktitle =	{24th International Symposium on Experimental Algorithms (SEA 2026)},
  pages =	{16:1--16:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-422-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{371},
  editor =	{Aum\"{u}ller, Martin and Finocchi, Irene},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2026.16},
  URN =		{urn:nbn:de:0030-drops-260204},
  doi =		{10.4230/LIPIcs.SEA.2026.16},
  annote =	{Keywords: compression, algorithm engineering, parallel computation}
}
Document
DOI: 10.4230/LIPIcs.CPM.2026.34
LZBE: An LZ-Style Compressor Supporting O(log n)-Time Random Access

Authors: Hiroki Shibata, Yuto Nakashima, Yutaro Yamaguchi, and Shunsuke Inenaga

Published in: LIPIcs, Volume 369, 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026)

Abstract
An LZ-like factorization of a string divides it into factors, each being either a single character or a copy of a preceding substring. While grammar-based compression schemes support efficient random access with space linear in the compressed size, no comparable guarantees are known for general LZ-like factorizations. This limitation motivated restricted variants such as LZ-End [Kreft and Navarro, 2013] and height-bounded LZ (LZHB) [Bannai et al., 2024], which trade off some compression efficiency for faster access. In this paper, we introduce LZ-Begin-End (LZBE), a new LZ-like variant in which every copy factor must refer to a contiguous sequence of preceding factors. This structural restriction ensures that any context-free grammar can be transformed into an LZBE factorization of the same size. We further study the greedy LZBE factorization, which selects each copy factor to be as long as possible while processing the input from left to right, and show that it can be computed in linear time. Moreover, we exhibit a family of strings for which the greedy LZBE factorization is asymptotically smaller than the smallest grammar. These results demonstrate that the LZBE scheme is strictly more expressive than grammar-based compression in the worst case. To support fast queries, we propose a data structure for LZBE-compressed strings that permits O(log n)-time random access within space linear in the compressed size, where n is the length of the input string.
Cite as

Hiroki Shibata, Yuto Nakashima, Yutaro Yamaguchi, and Shunsuke Inenaga. LZBE: An LZ-Style Compressor Supporting O(log n)-Time Random Access. In 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 369, pp. 34:1-34:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{shibata_et_al:LIPIcs.CPM.2026.34,
  author =	{Shibata, Hiroki and Nakashima, Yuto and Yamaguchi, Yutaro and Inenaga, Shunsuke},
  title =	{{LZBE: An LZ-Style Compressor Supporting O(log n)-Time Random Access}},
  booktitle =	{37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026)},
  pages =	{34:1--34:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-420-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{369},
  editor =	{Bille, Philip and Prezza, Nicola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2026.34},
  URN =		{urn:nbn:de:0030-drops-259609},
  doi =		{10.4230/LIPIcs.CPM.2026.34},
  annote =	{Keywords: data compression, Lempel-Ziv parsing, string algorithms, random access}
}
Document
DOI: 10.4230/LIPIcs.FORC.2026.6
Escaping the Subprime Trap in Algorithmic Lending

Authors: Adam Bouyamourn and Alexander Williams Tolbert

Published in: LIPIcs, Volume 368, 7th Symposium on Foundations of Responsible Computing (FORC 2026)

Abstract
Disparities in lending to minority applicants persist even as algorithmic lending finds widespread adoption. We study the role of risk-management constraints, specifically Value-at-Risk and Expected Shortfall, in inducing inequality in loan approval decisions, even among applicants who are equally creditworthy. We contribute an analysis of 431,551 loan applications recorded under the Home Mortgage Disclosure Act, illustrating that disparities in data quality are associated with higher rates of loan denial and higher interest rate spreads for Black borrowers. We develop a formal model in which a mainstream bank (low-interest) is more sensitive to variance risk than a subprime bank (high-interest). If the mainstream bank has an inflated prior belief about the variance of the minority group, it may deny that group credit indefinitely, never learning the true risk of lending to that group, while the subprime lender serves this population at higher rates. We call this "The Subprime Trap": an equilibrium in which minority borrowers can borrow only from high-cost lenders, even when they are as creditworthy as majority applicants. We show that a finite subsidy can help minority groups escape the trap by covering enough of the mainstream bank’s downside so that it can afford to lend to, and thereby learn the true risk of lending to, the minority group. Once the mainstream bank has observed sufficiently many loans, its beliefs converge to the true underlying risk, and competition drives down the interest rates of subprime loans.
Cite as

Adam Bouyamourn and Alexander Williams Tolbert. Escaping the Subprime Trap in Algorithmic Lending. In 7th Symposium on Foundations of Responsible Computing (FORC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 368, pp. 6:1-6:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bouyamourn_et_al:LIPIcs.FORC.2026.6,
  author =	{Bouyamourn, Adam and Tolbert, Alexander Williams},
  title =	{{Escaping the Subprime Trap in Algorithmic Lending}},
  booktitle =	{7th Symposium on Foundations of Responsible Computing (FORC 2026)},
  pages =	{6:1--6:27},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-419-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{368},
  editor =	{Lin, Huijia (Rachel)},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FORC.2026.6},
  URN =		{urn:nbn:de:0030-drops-259777},
  doi =		{10.4230/LIPIcs.FORC.2026.6},
  annote =	{Keywords: Algorithmic fairness, algorithmic lending, Risk management, Value-at-Risk, Algorithmic Philosophy}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.49
Algorithms for Euclidean Distance Matrix Completion: Exploiting Proximity to Triviality

Authors: Fedor V. Fomin, Petr A. Golovach, M. S. Ramanujan, and Saket Saurabh

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
In the d-Euclidean Distance Matrix Completion (d-EDMC) problem, one aims to determine whether a given partial matrix of pairwise distances can be extended to a full Euclidean distance matrix in d dimensions. This problem is a cornerstone of computational geometry with numerous applications. While classical work on this problem often focuses on exploiting connections to semidefinite programming typically leading to approximation algorithms, we focus on exact algorithms and propose a novel distance-from-triviality parameterization framework to obtain tractability results for d-EDMC. We identify key structural patterns in the input that capture entry density, including chordal substructures and coverability of specified entries by fully specified principal submatrices. We obtain: 1) The first fixed-parameter algorithm (FPT algorithm) for d-EDMC parameterized by d and the maximum number of unspecified entries per row/column. This is achieved through a novel compression algorithm that reduces a given instance to a submatrix on 𝒪(1) rows (for fixed values of the parameters). 2) The first FPT algorithm for d-EDMC parameterized by d and the minimum number of fully specified principal submatrices whose entries cover all specified entries of the given matrix. This result is also achieved through a compression algorithm. 3) A polynomial-time algorithm for d-EDMC when both d and the minimum fill-in of a natural graph representing the specified entries are fixed constants. This result is achieved by combining tools from distance geometry and algorithms from real algebraic geometry. Our work identifies interesting parallels between EDM completion and graph problems, with our algorithms exploiting techniques from both domains.
Cite as

Fedor V. Fomin, Petr A. Golovach, M. S. Ramanujan, and Saket Saurabh. Algorithms for Euclidean Distance Matrix Completion: Exploiting Proximity to Triviality. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 49:1-49:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{fomin_et_al:LIPIcs.SoCG.2026.49,
  author =	{Fomin, Fedor V. and Golovach, Petr A. and Ramanujan, M. S. and Saurabh, Saket},
  title =	{{Algorithms for Euclidean Distance Matrix Completion: Exploiting Proximity to Triviality}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{49:1--49:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.49},
  URN =		{urn:nbn:de:0030-drops-258552},
  doi =		{10.4230/LIPIcs.SoCG.2026.49},
  annote =	{Keywords: Parameterized Complexity, Euclidean Embedding, Polynomial Compression}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.52
Online Packing of Orthogonal Polygons

Authors: Tim Gerlach, Benjamin Hennies, and Linda Kleist

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
While rectangular and box-shaped objects dominate the classic discourse of theoretic investigations, a fascinating frontier lies in packing more complex shapes. Given recent insights that convex polygons do not allow for constant competitive online algorithms for diverse variants under translation, we study orthogonal polygons, in particular of small complexity. For translational packings of orthogonal 6-gons, we show that the competitive ratio of any online algorithm that aims to pack the items into a minimal number of unit bins is in Ω(n/(log n)), where n denotes the number of objects. In contrast, we show that constant competitive algorithms exist when the orthogonal 6-gons are symmetric or small. For (orthogonally convex) orthogonal 8-gons, we show that the trivial n-competitive algorithm, which places each item in its own bin, is best-possible, i.e., every online algorithm has an asymptotic competitive ratio of at least n. This implies that for general orthogonal polygons, the trivial algorithm is best possible. Interestingly, for packing degenerate orthogonal polygons (with thickness 0), called skeletons, the change in complexity is even more drastic. While constant competitive algorithms for 6-skeletons exist, no online algorithm for 8-skeletons achieves a competitive ratio better than n. For other packing variants of orthogonal 6-gons under translation, our insights imply the following consequences. The asymptotic competitive ratio of any online algorithm is in Ω(n/(log n)) for strip packing, and there exist online algorithms with competitive ratios in O(1) for perimeter packing, or in O(√n) for minimizing the area of the bounding box. Moreover, the critical packing density is positive (if every object individually fits into the interior of a unit bin).
Cite as

Tim Gerlach, Benjamin Hennies, and Linda Kleist. Online Packing of Orthogonal Polygons. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 52:1-52:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{gerlach_et_al:LIPIcs.SoCG.2026.52,
  author =	{Gerlach, Tim and Hennies, Benjamin and Kleist, Linda},
  title =	{{Online Packing of Orthogonal Polygons}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{52:1--52:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.52},
  URN =		{urn:nbn:de:0030-drops-258589},
  doi =		{10.4230/LIPIcs.SoCG.2026.52},
  annote =	{Keywords: Packing, orthogonal polygon, algorithm, offline, online, competitive ratio, bin packing, strip packing, perimeter packing, critical density, 6-gon, 8-gon, L-shape, Z-shape, skeleton}
}
Document
Media Exposition
DOI: 10.4230/LIPIcs.SoCG.2026.98
Interactive Uniform Floodlight Illumination and Rotating Rays Voronoi Diagrams (Media Exposition)

Authors: Carlos Alegría, Ioannis Mantas, Marko Savić, and Martin Suderland

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
Floodlight illumination problems are art-gallery variants, where a target domain needs to be illuminated by guards, each associated with a field of view. The rotating rays Voronoi diagram is a Voronoi diagram with rays as sites under the angular distance. There is a natural connection of this Voronoi structure with the problem of finding the minimum aperture such that a given set of uniform aperture floodlights illuminates a target domain. In this work we present an interactive visualization software for such problems, supporting different angular distances, namely, oriented and unoriented versions, and for different domains, namely, the plane and simple polygons.
Cite as

Carlos Alegría, Ioannis Mantas, Marko Savić, and Martin Suderland. Interactive Uniform Floodlight Illumination and Rotating Rays Voronoi Diagrams (Media Exposition). In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 98:1-98:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{alegria_et_al:LIPIcs.SoCG.2026.98,
  author =	{Alegr{\'\i}a, Carlos and Mantas, Ioannis and Savi\'{c}, Marko and Suderland, Martin},
  title =	{{Interactive Uniform Floodlight Illumination and Rotating Rays Voronoi Diagrams}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{98:1--98:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.98},
  URN =		{urn:nbn:de:0030-drops-259048},
  doi =		{10.4230/LIPIcs.SoCG.2026.98},
  annote =	{Keywords: rotating rays Voronoi diagram, oriented angular distance, unoriented angular distance, Brocard angle, floodlight illumination, coverage problems, visualization software}
}
Document
Media Exposition
DOI: 10.4230/LIPIcs.SoCG.2026.100
Visualizing Higher Order Structures, Overlap Regions, and Clustering in the Hilbert Geometry (Media Exposition)

Authors: Hridhaan Banerjee, Soren Brown, June Cagan, Auguste H. Gezalyan, Megan Hunleth, Veena Kailad, Chaewoon Kyoung, Rowan Shigeno, Yasmine Tajeddin, Andrew Wagger, Kelin Zhu, and David M. Mount

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
Higher-order Voronoi diagrams and Delaunay mosaics in polygonal metrics have only recently been studied, yet no tools exist for visualizing them. We introduce a tool that fills this gap, providing dynamic interactive software for visualizing higher-order Voronoi diagrams and Delaunay mosaics along with clustering and tools for exploring overlap and outer regions in the Hilbert polygonal metric. We prove that k-th order Voronoi cells are not always star-shaped and establish complexity bounds for our algorithm, which generates all order Voronoi diagrams at once. Our software unifies and extends previous tools for visualizing the Hilbert, Funk, and Thompson geometries.
Cite as

Hridhaan Banerjee, Soren Brown, June Cagan, Auguste H. Gezalyan, Megan Hunleth, Veena Kailad, Chaewoon Kyoung, Rowan Shigeno, Yasmine Tajeddin, Andrew Wagger, Kelin Zhu, and David M. Mount. Visualizing Higher Order Structures, Overlap Regions, and Clustering in the Hilbert Geometry (Media Exposition). In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 100:1-100:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{banerjee_et_al:LIPIcs.SoCG.2026.100,
  author =	{Banerjee, Hridhaan and Brown, Soren and Cagan, June and Gezalyan, Auguste H. and Hunleth, Megan and Kailad, Veena and Kyoung, Chaewoon and Shigeno, Rowan and Tajeddin, Yasmine and Wagger, Andrew and Zhu, Kelin and Mount, David M.},
  title =	{{Visualizing Higher Order Structures, Overlap Regions, and Clustering in the Hilbert Geometry}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{100:1--100:6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.100},
  URN =		{urn:nbn:de:0030-drops-259062},
  doi =		{10.4230/LIPIcs.SoCG.2026.100},
  annote =	{Keywords: Hilbert metric, Funk metric, Voronoi diagrams}
}
Document
DOI: 10.4230/LITES.11.1.1
A Survey of Real-Time Support, Analysis, and Advancements in ROS 2

Authors: Daniel Casini, Jian-Jia Chen, Jing Li, Federico Reghenzani, and Harun Teper

Published in: LITES, Volume 11, Issue 1 (2026). Leibniz Transactions on Embedded Systems, Volume 11, Issue 1

Abstract
The Robot Operating System 2 (ROS 2) has emerged as a relevant middleware framework for robotic applications, offering modularity, distributed execution, and communication. In the last six years, ROS 2 has drawn increasing attention from the real-time systems community and industry. This survey presents a comprehensive overview of research efforts that analyze, enhance, and extend ROS 2 to support real-time execution. We first provide a detailed description of the internal scheduling mechanisms of ROS 2 and its layered architecture, including the interaction with DDS-based communication and other communication middleware. We then review key contributions from the literature, covering timing analysis for both single- and multi-threaded executors, metrics such as response time, reaction time, and data age, and different communication modes. The survey also discusses community-driven enhancements to the ROS 2 runtime, including new executor algorithm designs, real-time GPU management, and microcontroller support via micro-ROS. Furthermore, we summarize techniques for bounding DDS communication delays, message filters, and profiling tools that have been developed to support analysis and experimentation. To help systematize this growing body of work, we introduce taxonomies that classify the surveyed contributions based on different criteria. This survey aims to guide both researchers and practitioners in understanding and improving the real-time capabilities of ROS 2.
Cite as

Daniel Casini, Jian-Jia Chen, Jing Li, Federico Reghenzani, and Harun Teper. A Survey of Real-Time Support, Analysis, and Advancements in ROS 2. In LITES, Volume 11, Issue 1 (2026). Leibniz Transactions on Embedded Systems, Volume 11, Issue 1, pp. 1:1-1:37, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@Article{casini_et_al:LITES.11.1.1,
  author =	{Casini, Daniel and Chen, Jian-Jia and Li, Jing and Reghenzani, Federico and Teper, Harun},
  title =	{{A Survey of Real-Time Support, Analysis, and Advancements in ROS 2}},
  journal =	{Leibniz Transactions on Embedded Systems},
  pages =	{1:1--1:37},
  ISSN =	{2199-2002},
  year =	{2026},
  volume =	{11},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LITES.11.1.1},
  URN =		{urn:nbn:de:0030-drops-257914},
  doi =		{10.4230/LITES.11.1.1},
  annote =	{Keywords: ROS 2, middleware, real-time, timing predictability, publish-subscribe}
}
Document
DOI: 10.4230/LIPIcs.FUN.2026.11
An Almost-Optimal Upper Bound on the Push Number of the Torus Puzzle

Authors: Matteo Caporrella and Stefano Leucci

Published in: LIPIcs, Volume 366, 13th International Conference on Fun with Algorithms (FUN 2026)

Abstract
We study the Torus Puzzle, a solitaire game in which the elements of an input m × n matrix need to be rearranged into a target configuration via a sequence of unit rotations (i.e., circular shifts) of rows and/or columns. Amano et al. proposed a more permissive variant of the above puzzle, where each row and column rotation can shift the involved elements by any amount of positions. The number of rotations needed to solve the original and the permissive variants of the puzzle are respectively known as the push number and the drag number, where the latter is always smaller than or equal to the former and admits an existential lower bound of Ω(mn). While this lower bound is matched by an O(mn) upper bound, the push number is not so well understood. Indeed, to the best of our knowledge, only an O(mn ⋅ max{m, n}) upper bound is currently known. In this paper, we provide an algorithm that solves the Torus Puzzle using O(mn ⋅ log max {m, n}) unit rotations in a model that is more restricted than that of the original puzzle. This implies a corresponding upper bound on the push number and reduces the gap between the known upper and lower bounds from Θ(max{m,n}) to Θ(log max{m, n}).
Cite as

Matteo Caporrella and Stefano Leucci. An Almost-Optimal Upper Bound on the Push Number of the Torus Puzzle. In 13th International Conference on Fun with Algorithms (FUN 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 366, pp. 11:1-11:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{caporrella_et_al:LIPIcs.FUN.2026.11,
  author =	{Caporrella, Matteo and Leucci, Stefano},
  title =	{{An Almost-Optimal Upper Bound on the Push Number of the Torus Puzzle}},
  booktitle =	{13th International Conference on Fun with Algorithms (FUN 2026)},
  pages =	{11:1--11:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-417-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{366},
  editor =	{Iacono, John},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2026.11},
  URN =		{urn:nbn:de:0030-drops-257307},
  doi =		{10.4230/LIPIcs.FUN.2026.11},
  annote =	{Keywords: Torus puzzle, Push number, Permutation puzzles}
}
Document
DOI: 10.4230/LIPIcs.FUN.2026.29
Finding Shortest Walks in Kuru Kuru Kururin

Authors: Mickaël Laurent and Maher Mallem

Published in: LIPIcs, Volume 366, 13th International Conference on Fun with Algorithms (FUN 2026)

Abstract
This paper serves as a celebration of the twenty-fifth anniversary of Kuru Kuru Kururin. Although this video game is presented as a collection of two-dimensional puzzles based on rotation, it naturally invites players to complete its levels as quickly as possible. This has led to a surprisingly rich and challenging playing field to finding foremost temporal walks. In this work, we tackle this problem both in theory and in practice. First, we introduce a model for the game and provide an in-depth complexity analysis. Most notably, we show how each gameplay mechanic independently brings a layer of NP-hardness and/or co-NP-hardness. We also provide a pseudo-polynomial time algorithm for the general problem and identify several cases which can be solved in polynomial time. Along the way, we discuss connections to the more established framework of temporal graphs, both in the point model and the interval model. Then, we propose simple and flexible algorithmic techniques to reduce state space and guide the search, offering trade-offs between precision and computation speed in practice. These techniques were implemented and tested using a full recreation of the game physics and the levels from the original game. We demonstrate the efficiency of our framework in several settings - with or without taking damage, with or without unintended game mechanics - and relate empirical struggles which we encountered in practice to our complexity analysis. Our implementation is open source and fully available online, offering a novel and amusing setting to benchmark shortest path algorithms.
Cite as

Mickaël Laurent and Maher Mallem. Finding Shortest Walks in Kuru Kuru Kururin. In 13th International Conference on Fun with Algorithms (FUN 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 366, pp. 29:1-29:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{laurent_et_al:LIPIcs.FUN.2026.29,
  author =	{Laurent, Micka\"{e}l and Mallem, Maher},
  title =	{{Finding Shortest Walks in Kuru Kuru Kururin}},
  booktitle =	{13th International Conference on Fun with Algorithms (FUN 2026)},
  pages =	{29:1--29:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-417-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{366},
  editor =	{Iacono, John},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2026.29},
  URN =		{urn:nbn:de:0030-drops-257480},
  doi =		{10.4230/LIPIcs.FUN.2026.29},
  annote =	{Keywords: Shortest path, Complexity}
}
Document
DOI: 10.4230/OASIcs.NINeS.2026.21
Accio: Rethinking OS-Architecture Co-Design for Next-Gen I/O

Authors: Amirmohammad Nazari, Rajit Manohar, and Robert Soulé

Published in: OASIcs, Volume 139, 1st New Ideas in Networked Systems (NINeS 2026)

Abstract
In this paper, we propose a novel software/hardware design to improve I/O performance while maintaining existing POSIX-standard APIs. Our approach stands in contrast to existing kernel-bypass strategies that improve performance at the expense of abandoning familiar programming abstractions. Our key insight is that navigating the performance-functionality trade-off requires changes to the processor; it cannot be done without support of the CPU micro-architecture. Our design, called Accio, includes: dedicated hardware for interrupt management, a hardware assist for thread scheduling, tables in hardware that manage I/O state, and modifications to the operating system to support the new hardware. Our evaluation demonstrates that Accio saturates the bus bandwidth, reduces CPU usage by up to 66% compared to state-of-the-art kernel-bypass systems, and reduces latency to 1/12th of that of the Linux kernel, matching that of kernel-bypass systems.
Cite as

Amirmohammad Nazari, Rajit Manohar, and Robert Soulé. Accio: Rethinking OS-Architecture Co-Design for Next-Gen I/O. In 1st New Ideas in Networked Systems (NINeS 2026). Open Access Series in Informatics (OASIcs), Volume 139, pp. 21:1-21:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{nazari_et_al:OASIcs.NINeS.2026.21,
  author =	{Nazari, Amirmohammad and Manohar, Rajit and Soul\'{e}, Robert},
  title =	{{Accio: Rethinking OS-Architecture Co-Design for Next-Gen I/O}},
  booktitle =	{1st New Ideas in Networked Systems (NINeS 2026)},
  pages =	{21:1--21:24},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-414-7},
  ISSN =	{2190-6807},
  year =	{2026},
  volume =	{139},
  editor =	{Argyraki, Katerina and Panda, Aurojit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.NINeS.2026.21},
  URN =		{urn:nbn:de:0030-drops-256063},
  doi =		{10.4230/OASIcs.NINeS.2026.21},
  annote =	{Keywords: Networks, Operating Systems, I/O Optimization}
}
Document
DOI: 10.4230/LIPIcs.STACS.2026.24
Foremost, Fastest, Shortest: Temporal Graph Realization Under Various Path Metrics

Authors: Justine Cauvi, Nils Morawietz, and Laurent Viennot

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
In this work, we follow the current trend on temporal graph realization, where one is given a property P and the goal is to determine whether there is a temporal graph, that is, a graph where the edge set changes over time, with property P. We consider the problems where the given property P is a prescribed matrix for the duration, length, or earliest arrival time of pairwise temporal paths. This means that we are given a matrix D and ask whether there is a temporal graph such that for any ordered pair of vertices (s,t), D_{s,t} equals the duration (length, or earliest arrival time, respectively) of any temporal path from s to t minimizing that specific temporal path metric. For shortest and earliest arrival temporal paths, we are the first to consider these problems as far as we know. We analyze these problems for many settings such as: strict and non-strict paths, periodic and non-periodic temporal graphs, and limited number of labels per edge (limited number of occurrences per edge over time). In contrast to all other path metrics, we show that for the earliest arrival times, we can achieve polynomial-time algorithms in periodic and non-periodic temporal graphs and for strict and and non-strict paths. However, the problem becomes NP-hard when the matrix does not contain a single integer but a set or range of possible allowed values. As we show, the problem can still be solved efficiently in this scenario, when the number of entries with more than one value is small, that is, we develop an FPT-algorithm for the number of such entries. For the setting of fastest paths, we achieve new hardness results that answers an open question by Klobas, Mertzios, Molter, and Spirakis [Theor. Comput. Sci. '25] about the parameterized complexity of the problem with respect to the vertex cover number and significantly improves over a previous hardness result for the feedback vertex set number. When considering shortest paths, we show that the periodic versions are polynomial-time solvable whereas the non-periodic versions become NP-hard.
Cite as

Justine Cauvi, Nils Morawietz, and Laurent Viennot. Foremost, Fastest, Shortest: Temporal Graph Realization Under Various Path Metrics. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 24:1-24:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{cauvi_et_al:LIPIcs.STACS.2026.24,
  author =	{Cauvi, Justine and Morawietz, Nils and Viennot, Laurent},
  title =	{{Foremost, Fastest, Shortest: Temporal Graph Realization Under Various Path Metrics}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{24:1--24:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.24},
  URN =		{urn:nbn:de:0030-drops-255139},
  doi =		{10.4230/LIPIcs.STACS.2026.24},
  annote =	{Keywords: network design, temporal paths, foremost paths, fastest paths, shortest paths, non-strict paths, periodic temporal graphs}
}
Document
DOI: 10.4230/LIPIcs.STACS.2026.19
A Linear Kernel for Independent Set Reconfiguration in Planar Graphs

Authors: Nicolas Bousquet and Daniel W. Cranston

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
Fix a positive integer r, and a graph G that is K_{3,r}-minor-free. Let I_s and I_t be two independent sets in G, each of size k. We begin with a "token" on each vertex of I_s and seek to move all tokens to I_t, by repeated "token jumping", removing a single token from one vertex and placing it on another vertex. We require that each intermediate arrangement of tokens again specifies an independent set of size k. Given G, I_s, and I_t, we ask whether there exists a sequence of token jumps that transforms I_s into I_t. When k is part of the input, this problem is known to be PSPACE-complete. But it was shown by Ito, Kamiński, and Ono [Ito et al., 2014] to be fixed-parameter tractable. That is, the problem can be solved in time f(k)⋅ P(n), for some function f and polynomial P, where n denotes the order of G. Here we strengthen the upper bound on the running time in terms of k by showing that the problem has a kernel of size linear in k. More precisely, we transform an arbitrary input problem on a K_{3,r}-minor-free graph (for some fixed positive integer r) into an equivalent problem on a (K_{3,r}-minor-free) graph with order O(k). This answers positively a question of Bousquet, Mouawad, Nishimura, and Siebertz [Nicolas Bousquet et al., 2022] and improves the recent quadratic kernel of Cranston, Mühlenthaler, and Peyrille [Daniel W. Cranston et al., 2024]. For planar graphs, we further strengthen this upper bound to get a kernel of size at most 42k.
Cite as

Nicolas Bousquet and Daniel W. Cranston. A Linear Kernel for Independent Set Reconfiguration in Planar Graphs. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 19:1-19:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bousquet_et_al:LIPIcs.STACS.2026.19,
  author =	{Bousquet, Nicolas and Cranston, Daniel W.},
  title =	{{A Linear Kernel for Independent Set Reconfiguration in Planar Graphs}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{19:1--19:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.19},
  URN =		{urn:nbn:de:0030-drops-255081},
  doi =		{10.4230/LIPIcs.STACS.2026.19},
  annote =	{Keywords: Reconfiguration, Independent Set, Kernel, Planar graphs}
}
  • Refine by Type
  • 136 Document/PDF
  • 114 Document/HTML

  • Refine by Publication Year
  • 22 2026
  • 92 2025
  • 1 2024
  • 2 2023
  • 1 2021
  • Show More...

  • Refine by Author
  • 7 Morawietz, Nils
  • 5 Fomin, Fedor V.
  • 5 Golovach, Petr A.
  • 5 Saurabh, Saket
  • 4 Zehavi, Meirav
  • Show More...

  • Refine by Series/Journal
  • 122 LIPIcs
  • 5 OASIcs
  • 5 LITES
  • 2 TGDK
  • 2 DagSemProc

  • Refine by Classification
  • 26 Theory of computation → Parameterized complexity and exact algorithms
  • 15 Theory of computation → Design and analysis of algorithms
  • 12 Theory of computation → Computational geometry
  • 12 Theory of computation → Graph algorithms analysis
  • 9 Mathematics of computing → Graph algorithms
  • Show More...

  • Refine by Keyword
  • 9 parameterized complexity
  • 7 Parameterized Complexity
  • 7 Treewidth
  • 4 Parameterized complexity
  • 3 Approximation Algorithms
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact