33 Search Results for "Scheffer, Christian"

Document
DOI: 10.4230/LIPIcs.SoCG.2026.43
Unlabeled Multi-Robot Motion Planning with Improved Separation Trade-Offs

Authors: Tsuri Farhana, Omrit Filtser, and Shalev Goldshtein

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

Abstract
We study unlabeled multi-robot motion planning for unit-disk robots in a polygonal environment. Although the problem is hard in general, polynomial-time solutions exist under appropriate separation assumptions on start and target positions. Solovey et al. (RSS'15) provide a near-optimal solution assuming that start/target positions must have pairwise distance at least 4, and at least √5≈2.236 from obstacles. This raises the question of whether polynomial-time algorithms can be obtained in even more densely packed environments. In this paper we present a generalized algorithm that achieve different trade-offs on the robots-separation and obstacles-separation bounds, all significantly improving upon the state of the art. Specifically, we obtain polynomial-time constant-approximation algorithms to minimize the total path length when (i) the robots-separation is 2 2/3 and the obstacles-separation is 1 2/3, or (ii) the robots-separation is ≈3.291 and the obstacles-separation ≈1.354. Additionally, we introduce a different strategy yielding a polynomial-time solution when the robots-separation is only 2, and the obstacles-separation is 3. Finally, we show that without any robots-separation assumption, obstacles-separation of at least 1.5 may be necessary for a solution to exist.
Cite as

Tsuri Farhana, Omrit Filtser, and Shalev Goldshtein. Unlabeled Multi-Robot Motion Planning with Improved Separation Trade-Offs. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 43:1-43:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{farhana_et_al:LIPIcs.SoCG.2026.43,
  author =	{Farhana, Tsuri and Filtser, Omrit and Goldshtein, Shalev},
  title =	{{Unlabeled Multi-Robot Motion Planning with Improved Separation Trade-Offs}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{43:1--43:16},
  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.43},
  URN =		{urn:nbn:de:0030-drops-258495},
  doi =		{10.4230/LIPIcs.SoCG.2026.43},
  annote =	{Keywords: multi-robot motion planning}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.46
A Branch-And-Bound Algorithm for the Traveling Salesman Problem with Difficult Neighborhoods

Authors: Sándor P. Fekete, Rouven Kniep, Dominik Krupke, and Michael Perk

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

Abstract
The Traveling Salesman Problem with Neighborhoods (TSPN) generalizes the classical Traveling Salesman Problem (TSP) by requiring a tour to visit a set of polygonal regions rather than fixed points, a natural goal that arises in various applications. While the geometric TSP allows arbitrarily close approximation and provably optimal solutions for benchmark instances of significant size, the TSPN is considerably more challenging, both in theory (due to APX-hardness) and practice, for which only benchmark instances up to 16 regions have been solved to optimality. Here we present a branch-and-bound algorithm that combines a spectrum of geometry-based filters (for reducing the number of considered sequences) with Second-Order Cone Programs (SOCP) (for computing optimal tours for a given permutation of neighborhoods). This allows us to solve larger polygonal TSPN instances than before to within an optimality tolerance of 0.1%; moreover, while previous work (both in theory and practice) relied on relatively benign neighborhoods, we can handle non-convex, non-simple neighborhoods of different sizes. In experiments on 490 benchmark instances with up to 50 polygons each, our method achieves a 99.6% optimality rate within 300s, with the remaining two instances solved within 595s. For 68 larger instances of size n = 60, our method still allows solving 86.8% of instances to optimality within 900s, leaving only 3 of the instances with optimality gaps above 3%, with the maximum being 5.53%.
Cite as

Sándor P. Fekete, Rouven Kniep, Dominik Krupke, and Michael Perk. A Branch-And-Bound Algorithm for the Traveling Salesman Problem with Difficult Neighborhoods. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 46:1-46:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{fekete_et_al:LIPIcs.SoCG.2026.46,
  author =	{Fekete, S\'{a}ndor P. and Kniep, Rouven and Krupke, Dominik and Perk, Michael},
  title =	{{A Branch-And-Bound Algorithm for the Traveling Salesman Problem with Difficult Neighborhoods}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{46:1--46:20},
  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.46},
  URN =		{urn:nbn:de:0030-drops-258529},
  doi =		{10.4230/LIPIcs.SoCG.2026.46},
  annote =	{Keywords: Geometric optimization, geometric covering, TSP with neighborhoods, exact algorithms, algorithm engineering}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.44
Tilt Automata: Gathering Particles with Uniform External Control

Authors: Sándor P. Fekete, Jonas Friemel, Peter Kramer, Jan-Marc Reinhardt, Christian Rieck, and Christian Scheffer

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

Abstract
Motivated by targeted drug delivery, we investigate the gathering of particles in the full tilt model of externally controlled motion planning: A set of particles is located at the tiles of a polyomino with all particles reacting uniformly to an external force by moving as far as possible in one of the four axis-parallel directions until they hit the boundary. The goal is to choose a sequence of directions that moves all particles to a common position. Our results include a polynomial-time algorithm for gathering in a completely filled polyomino as well as hardness reductions for approximating shortest gathering sequences and for determining whether the particles in a partially filled polyomino can be gathered. We pay special attention to the impact of restricted geometry, particularly polyominoes without holes. As a corollary, we make progress on an open question from [Balanza-Martinez et al., SODA 2020] by showing that deciding whether a given position can be occupied remains NP-hard in polyominoes without holes. Our results build on a connection we establish between tilt models and the theory of synchronizing automata.
Cite as

Sándor P. Fekete, Jonas Friemel, Peter Kramer, Jan-Marc Reinhardt, Christian Rieck, and Christian Scheffer. Tilt Automata: Gathering Particles with Uniform External Control. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 44:1-44:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{fekete_et_al:LIPIcs.SoCG.2026.44,
  author =	{Fekete, S\'{a}ndor P. and Friemel, Jonas and Kramer, Peter and Reinhardt, Jan-Marc and Rieck, Christian and Scheffer, Christian},
  title =	{{Tilt Automata: Gathering Particles with Uniform External Control}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{44:1--44:19},
  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.44},
  URN =		{urn:nbn:de:0030-drops-258508},
  doi =		{10.4230/LIPIcs.SoCG.2026.44},
  annote =	{Keywords: Uniform control, gathering, full tilt, polyominoes, synchronizing automata}
}
Document
Research
DOI: 10.4230/TGDK.4.1.1
On the Computational Cost of Knowledge Graph Embeddings

Authors: Victor Charpenay, Mansour Zoubeirou A Mayaki, and Antoine Zimmermann

Published in: TGDK, Volume 4, Issue 1 (2026). Transactions on Graph Data and Knowledge, Volume 4, Issue 1

Abstract
Over a decade, numerous Knowledge Graph Embedding (KGE) models have been designed and evaluated on reference datasets, always with increasing performance. In this paper, we re-evaluate these models with respect to their computational efficiency during training, by estimating the computational cost of the procedure expressed in floating-point operations. We design a cost model based on analytical expressions and apply it on a collection of 20 KGE models, representative of the state-of-the-art. We show that dimensionality or parameter efficiency, used in the literature to compare models with each other, are not suitable to evaluate the true cost of models. Through fixed-budget experiments, a novel approach to evaluate KGE models based on cost estimates, we re-assess the relative performance of model families compared to the state-of-the-art. Bilinear models such as ComplEx underperform with a low computational budget while hyperbolic linear models appear to offer no particular benefit compared to simpler Euclidian models, especially the MuRE model. Neural models, such as ConvE or CompGCN, achieve reasonable performance in the literature but their high computational cost appears unnecessary when compared with other models. The trade-off between efficiency and expressivity of both linear and neural models is to be further explored.
Cite as

Victor Charpenay, Mansour Zoubeirou A Mayaki, and Antoine Zimmermann. On the Computational Cost of Knowledge Graph Embeddings. In Transactions on Graph Data and Knowledge (TGDK), Volume 4, Issue 1, pp. 1:1-1:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@Article{charpenay_et_al:TGDK.4.1.1,
  author =	{Charpenay, Victor and Zoubeirou A Mayaki, Mansour and Zimmermann, Antoine},
  title =	{{On the Computational Cost of Knowledge Graph Embeddings}},
  journal =	{Transactions on Graph Data and Knowledge},
  pages =	{1:1--1:30},
  ISSN =	{2942-7517},
  year =	{2026},
  volume =	{4},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/TGDK.4.1.1},
  URN =		{urn:nbn:de:0030-drops-256863},
  doi =		{10.4230/TGDK.4.1.1},
  annote =	{Keywords: Knowledge Graph Embedding, Parameter Efficiency, Computational Budget, Green AI}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.14
General Computation Using Slidable Tiles with Deterministic Global Forces

Authors: Alberto Avila-Jimenez, David Barreda, Sarah-Laurie Evans, Austin Luchsinger, Aiden Massie, Robert Schweller, Evan Tomai, and Tim Wylie

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
We study the computational power of the Full-Tilt model of motion planning, where slidable polyominos are moved maximally around a board by way of a sequence of directional "tilts." We focus on the deterministic scenario in which the tilts constitute a repeated clockwise rotation. We show that general-purpose computation is possible within this framework by providing a direct and efficient simulation of space-bounded Turing machines in which one computational step of the machine is simulated per O(1) rotations. We further show that the initial tape of the machine can be programmed by an initial tilt-sequence preceding the rotations. This result immediately implies new PSPACE-completeness results for the well-studied problems of occupancy (deciding if a given board location can be occupied by a tile), vacancy (deciding if a location can be emptied), relocation (deciding if a tile can be moved from one location to another), and reconfiguration (can a given board configuration be reconfigured into a second given configuration) that hold even for deterministically repeating tilt cycles such as rotations. All of our PSPACE-completeness results hold even when there is only a single domino in the system beyond singleton tiles. Following, we show that these results work in the Single-Step tilt model for larger constant cycles. We then investigate computational efficiency by showing a modification to implement a two-tape Turing machine in the Full-Tilt model and Systolic Arrays in the Single-Step model. Finally, we show a cyclic implementation for tilt-efficient Threshold Circuits.
Cite as

Alberto Avila-Jimenez, David Barreda, Sarah-Laurie Evans, Austin Luchsinger, Aiden Massie, Robert Schweller, Evan Tomai, and Tim Wylie. General Computation Using Slidable Tiles with Deterministic Global Forces. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 14:1-14:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{avilajimenez_et_al:LIPIcs.ITCS.2026.14,
  author =	{Avila-Jimenez, Alberto and Barreda, David and Evans, Sarah-Laurie and Luchsinger, Austin and Massie, Aiden and Schweller, Robert and Tomai, Evan and Wylie, Tim},
  title =	{{General Computation Using Slidable Tiles with Deterministic Global Forces}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{14:1--14:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.14},
  URN =		{urn:nbn:de:0030-drops-253019},
  doi =		{10.4230/LIPIcs.ITCS.2026.14},
  annote =	{Keywords: motion planning, global control, external forces, deterministic computation, occupancy, vacancy}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.46
Realizing Metric Spaces with Convex Obstacles

Authors: Sándor Kisfaludi-Bak and Leonidas Theocharous

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
The presence of obstacles has a significant impact on distance computation, motion-planning, and visibility. These problems have been studied extensively in the planar setting, while our understanding of these problems in 3- and higher-dimensional spaces is still rudimentary. In this paper, we study the impact of different types of obstacles on the induced geodesic metric in 3-dimensional Euclidean space. We say that a finite metric space (X, dist_X) is approximately realizable by a collection 𝒯 of obstacles in ℝ³ if for any ε > 0 it can be embedded into (ℝ³⧵⋃_{T∈𝒯} T, dist_𝒯) with worst-case multiplicative distortion 1+ε, where dist_𝒯 denotes the geodesic distance in the free space induced by 𝒯. We focus on three key geometric properties of obstacles -convexity, disjointness, and fatness- and examine how dropping each one of them affects the existence of such embeddings. Our main result concerns dropping the fatness property: we demonstrate that any finite metric space is realizable with 1+ε worst-case multiplicative distortion using a collection of convex and pairwise disjoint obstacles in ℝ³, even if the obstacles are congruent and equilateral triangles. Based on the same construction, we can also show that if we require fatness but drop any of the other two properties instead, then we can still approximately realize any finite metric space. Our results have important implications on the approximability of tsp with obstacles, a natural variant of tsp introduced recently by Alkema et al. (ESA 2022). Specifically, we use the recent results of Banerjee et al. on tsp in doubling spaces (FOCS 2024) and of Chew et al. on distances among obstacles (Inf. Process. Lett. 2002) to show that tsp with obstacles admits a PTAS if the obstacles are convex, fat, and pairwise disjoint. If any of these three properties is dropped, then our results, combined with the APX-hardness of Metric tsp, demonstrate that tsp with obstacles is APX-hard.
Cite as

Sándor Kisfaludi-Bak and Leonidas Theocharous. Realizing Metric Spaces with Convex Obstacles. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 46:1-46:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kisfaludibak_et_al:LIPIcs.ISAAC.2025.46,
  author =	{Kisfaludi-Bak, S\'{a}ndor and Theocharous, Leonidas},
  title =	{{Realizing Metric Spaces with Convex Obstacles}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{46:1--46:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.46},
  URN =		{urn:nbn:de:0030-drops-249545},
  doi =		{10.4230/LIPIcs.ISAAC.2025.46},
  annote =	{Keywords: traveling salesman, geodesic distance}
}
Document
Survey
DOI: 10.4230/TGDK.3.2.1
Resilience in Knowledge Graph Embeddings

Authors: Arnab Sharma, N'Dah Jean Kouagou, and Axel-Cyrille Ngonga Ngomo

Published in: TGDK, Volume 3, Issue 2 (2025). Transactions on Graph Data and Knowledge, Volume 3, Issue 2

Abstract
In recent years, knowledge graphs have gained interest and witnessed widespread applications in various domains, such as information retrieval, question-answering, recommendation systems, amongst others. Large-scale knowledge graphs to this end have demonstrated their utility in effectively representing structured knowledge. To further facilitate the application of machine learning techniques, knowledge graph embedding models have been developed. Such models can transform entities and relationships within knowledge graphs into vectors. However, these embedding models often face challenges related to noise, missing information, distribution shift, adversarial attacks, etc. This can lead to sub-optimal embeddings and incorrect inferences, thereby negatively impacting downstream applications. While the existing literature has focused so far on adversarial attacks on KGE models, the challenges related to the other critical aspects remain unexplored. In this paper, we, first of all, give a unified definition of resilience, encompassing several factors such as generalisation, in-distribution generalization, distribution adaption, and robustness. After formalizing these concepts for machine learning in general, we define them in the context of knowledge graphs. To find the gap in the existing works on resilience in the context of knowledge graphs, we perform a systematic survey, taking into account all these aspects mentioned previously. Our survey results show that most of the existing works focus on a specific aspect of resilience, namely robustness. After categorizing such works based on their respective aspects of resilience, we discuss the challenges and future research directions.
Cite as

Arnab Sharma, N'Dah Jean Kouagou, and Axel-Cyrille Ngonga Ngomo. Resilience in Knowledge Graph Embeddings. In Transactions on Graph Data and Knowledge (TGDK), Volume 3, Issue 2, pp. 1:1-1:38, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@Article{sharma_et_al:TGDK.3.2.1,
  author =	{Sharma, Arnab and Kouagou, N'Dah Jean and Ngomo, Axel-Cyrille Ngonga},
  title =	{{Resilience in Knowledge Graph Embeddings}},
  journal =	{Transactions on Graph Data and Knowledge},
  pages =	{1:1--1:38},
  ISSN =	{2942-7517},
  year =	{2025},
  volume =	{3},
  number =	{2},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/TGDK.3.2.1},
  URN =		{urn:nbn:de:0030-drops-248117},
  doi =		{10.4230/TGDK.3.2.1},
  annote =	{Keywords: Knowledge graphs, Resilience, Robustness}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.57
Improved Hardness-Of-Approximation for Token-Swapping

Authors: Sam Hiken and Nicole Wein

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
We study the token swapping problem, in which we are given a graph with an initial assignment of one distinct token to each vertex, and a final desired assignment (again with one token per vertex). The goal is to find the minimum length sequence of swaps of adjacent tokens required to get from the initial to the final assignment. The token swapping problem is known to be NP-complete. It is also known to have a polynomial-time 4-approximation algorithm. From the hardness-of-approximation side, it is known to be NP-hard to approximate with a ratio better than 1001/1000. Our main result is an improvement of the approximation ratio of the lower bound: We show that it is NP-hard to approximate with ratio better than 14/13. We then turn our attention to the 0/1-weighted version, in which every token has a weight of either 0 or 1, and the cost of a swap is the sum of the weights of the two participating tokens. Unlike standard token swapping, no constant-factor approximation is known for this version, and we provide an explanation. We prove that 0/1-weighted token swapping is NP-hard to approximate with ratio better than (1-ε) ln(n) for any constant ε > 0. Lastly, we prove two barrier results for the standard (unweighted) token swapping problem. We show that one cannot beat the current best known approximation ratio of 4 using a large class of algorithms which includes all known algorithms, nor can one beat it using a common analysis framework.
Cite as

Sam Hiken and Nicole Wein. Improved Hardness-Of-Approximation for Token-Swapping. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 57:1-57:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{hiken_et_al:LIPIcs.ESA.2025.57,
  author =	{Hiken, Sam and Wein, Nicole},
  title =	{{Improved Hardness-Of-Approximation for Token-Swapping}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{57:1--57:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.57},
  URN =		{urn:nbn:de:0030-drops-245251},
  doi =		{10.4230/LIPIcs.ESA.2025.57},
  annote =	{Keywords: algorithms, token-swapping, hardness-of-approximation, lower-bounds}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.28
Sliding Squares in Parallel

Authors: Hugo A. Akitaya, Sándor P. Fekete, Peter Kramer, Saba Molaei, Christian Rieck, Frederick Stock, and Tobias Wallner

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
We consider algorithmic problems motivated by modular robotic reconfiguration in the sliding square model, in which we are given n square-shaped modules in a (labeled or unlabeled) start configuration and need to find a schedule of sliding moves to transform it into a desired goal configuration, maintaining connectivity of the configuration at all times. Recent work has aimed at minimizing the total number of moves, resulting in fully sequential schedules that can perform reconfiguration in 𝒪(n²) moves, or 𝒪(nP) for arrangements of bounding box perimeter size P. We provide first results in the sliding square model that exploit parallel motion, performing reconfiguration in worst-case optimal makespan of 𝒪(P). We also provide tight bounds on the complexity of the problem by showing that even deciding the possibility of reconfiguration within makespan 1 is NP-complete in the unlabeled case. In the labeled variant, we note that deciding the same for makespan 2 is NP-complete, while makespan 1 is straightforward.
Cite as

Hugo A. Akitaya, Sándor P. Fekete, Peter Kramer, Saba Molaei, Christian Rieck, Frederick Stock, and Tobias Wallner. Sliding Squares in Parallel. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 28:1-28:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{a.akitaya_et_al:LIPIcs.ESA.2025.28,
  author =	{A. Akitaya, Hugo and Fekete, S\'{a}ndor P. and Kramer, Peter and Molaei, Saba and Rieck, Christian and Stock, Frederick and Wallner, Tobias},
  title =	{{Sliding Squares in Parallel}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{28:1--28:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.28},
  URN =		{urn:nbn:de:0030-drops-244961},
  doi =		{10.4230/LIPIcs.ESA.2025.28},
  annote =	{Keywords: Sliding squares, parallel motion, reconfigurability, motion planning, multi-agent path finding, makespan, swarm robotics, computational geometry}
}
Document
DOI: 10.4230/LIPIcs.WADS.2025.33
Spanner for the 0/1/∞ Weighted Region Problem

Authors: Joachim Gudmundsson, Zijin Huang, André van Renssen, and Sampson Wong

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

Abstract
We consider the problem of computing an approximate weighted shortest path in a weighted planar subdivision, with weights assigned from the set {0, 1, ∞}. The subdivision includes zero-cost regions (0-regions) with weight 0 and obstacles with weight ∞, all embedded in a plane with weight 1. In a polygonal domain, where the 0-regions and obstacles are non-overlapping polygons (not necessarily convex) with in total N vertices, we present an algorithm that computes a (1 + ε)-approximate spanner of the input vertices in expected Õ(N/ε³) time, for 0 < ε < 1. Using our spanner, we can compute a (1 + ε)-approximate weighted shortest path between any two points (not necessarily vertices) in Õ(N/ε³) time. Furthermore, we prove that our results more generally apply to non-polygonal convex regions. Using this generalisation, one can approximate the weak partial Fréchet similarity [Buchin et al., 2009] between two polygonal curves in expected Õ(n²/ε²) time, where n is the total number of vertices of the input curves.
Cite as

Joachim Gudmundsson, Zijin Huang, André van Renssen, and Sampson Wong. Spanner for the 0/1/∞ Weighted Region Problem. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 33:1-33:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gudmundsson_et_al:LIPIcs.WADS.2025.33,
  author =	{Gudmundsson, Joachim and Huang, Zijin and van Renssen, Andr\'{e} and Wong, Sampson},
  title =	{{Spanner for the 0/1/∞ Weighted Region Problem}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{33:1--33: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.33},
  URN =		{urn:nbn:de:0030-drops-242644},
  doi =		{10.4230/LIPIcs.WADS.2025.33},
  annote =	{Keywords: weighted region problem, approximate shortest path, spanner}
}
Artifact
Software
DOI: 10.4230/artifacts.24341
dispersive_agp_solver

Authors: Kai Kobbe and Dominik Krupke

Abstract
Cite as

Kai Kobbe, Dominik Krupke. dispersive_agp_solver (Software, Source Code). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-24341,
   title = {{dispersive\underlineagp\underlinesolver}}, 
   author = {Kobbe, Kai and Krupke, Dominik},
   note = {Software, German Research Foundation (DFG), project “CG:SHOP”, FE 407/21-1, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:f655f369c667ab3b9b7b7afff427303919d67cdc;origin=https://github.com/KaiKobbe/dispersive_agp_solver;visit=swh:1:snp:eb60401718e6b4aee843180c7288f8c3f6a39397;anchor=swh:1:rev:4a177bc942f444d2519f93d78eb23857f97eeb63}{\texttt{swh:1:dir:f655f369c667ab3b9b7b7afff427303919d67cdc}} (visited on 2025-08-20)},
   url = {https://github.com/KaiKobbe/dispersive_agp_solver},
   doi = {10.4230/artifacts.24341},
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.46
Guarding Offices with Maximum Dispersion

Authors: Sándor P. Fekete, Kai Kobbe, Dominik Krupke, Joseph S. B. Mitchell, Christian Rieck, and Christian Scheffer

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
We investigate the Dispersive Art Gallery Problem with vertex guards and rectangular visibility (r-visibility) for a class of orthogonal polygons that reflect the properties of real-world floor plans: these office-like polygons consist of rectangular rooms and corridors. In the dispersive variant of the Art Gallery Problem, the objective is not to minimize the number of guards but to maximize the minimum geodesic L₁-distance between any two guards, called the dispersion distance. Our main contributions are as follows. We prove that determining whether a vertex guard set can achieve a dispersion distance of 4 in office-like polygons is NP-complete, where vertices of the polygon are restricted to integer coordinates. Additionally, we present a simple worst-case optimal algorithm that guarantees a dispersion distance of 3 in polynomial time. Our complexity result extends to polyominoes, resolving an open question posed by Rieck and Scheffer [Christian Rieck and Christian Scheffer, 2024]. When vertex coordinates are allowed to be rational, we establish analogous results, proving that achieving a dispersion distance of 2+ε is NP-hard for any ε > 0, while the classic Art Gallery Problem remains solvable in polynomial time for this class of polygons. Furthermore, we give a straightforward polynomial-time algorithm that computes worst-case optimal solutions with a dispersion distance 2. On the other hand, for the more restricted class of hole-free independent office-like polygons, we propose a dynamic programming approach that computes optimal solutions. Moreover, we demonstrate that the problem is practically tractable for arbitrary orthogonal polygons. To this end, we compare solvers based on SAT, CP, and MIP formulations. Notably, SAT solvers efficiently compute optimal solutions for randomly generated instances with up to 1600 vertices in under 15s.
Cite as

Sándor P. Fekete, Kai Kobbe, Dominik Krupke, Joseph S. B. Mitchell, Christian Rieck, and Christian Scheffer. Guarding Offices with Maximum Dispersion. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 46:1-46:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{fekete_et_al:LIPIcs.MFCS.2025.46,
  author =	{Fekete, S\'{a}ndor P. and Kobbe, Kai and Krupke, Dominik and Mitchell, Joseph S. B. and Rieck, Christian and Scheffer, Christian},
  title =	{{Guarding Offices with Maximum Dispersion}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{46:1--46:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.46},
  URN =		{urn:nbn:de:0030-drops-241530},
  doi =		{10.4230/LIPIcs.MFCS.2025.46},
  annote =	{Keywords: Dispersive Art Gallery Problem, vertex guards, office-like polygons, orthogonal polygons, polyominoes, NP-completeness, worst-case optimality, dynamic programming, SAT solver}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.74
Drainability and Fillability of Polyominoes in Diverse Models of Global Control

Authors: Sándor P. Fekete, Peter Kramer, Jan-Marc Reinhardt, Christian Rieck, and Christian Scheffer

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
Tilt models offer intuitive and clean definitions of complex systems in which particles are influenced by global control commands. Despite a wide range of applications, there has been almost no theoretical investigation into the associated issues of filling and draining geometric environments. This is partly because a globally controlled system (i.e., passive matter) exhibits highly complex behavior that cannot be locally restricted. Thus, there is a strong need for theoretical studies that investigate these models both (1) in terms of relative power to each other, and (2) from a complexity theory perspective. In this work, we provide (1) general tools for comparing and contrasting different models of global control, and (2) both complexity and algorithmic results on filling and draining.
Cite as

Sándor P. Fekete, Peter Kramer, Jan-Marc Reinhardt, Christian Rieck, and Christian Scheffer. Drainability and Fillability of Polyominoes in Diverse Models of Global Control. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 74:1-74:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{fekete_et_al:LIPIcs.ICALP.2025.74,
  author =	{Fekete, S\'{a}ndor P. and Kramer, Peter and Reinhardt, Jan-Marc and Rieck, Christian and Scheffer, Christian},
  title =	{{Drainability and Fillability of Polyominoes in Diverse Models of Global Control}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{74:1--74:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.74},
  URN =		{urn:nbn:de:0030-drops-234518},
  doi =		{10.4230/LIPIcs.ICALP.2025.74},
  annote =	{Keywords: Global control, full Tilt, single Tilt, Fillability, Drainability, Polyominoes, Complexity}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.44
A Minor-Testing Approach for Coordinated Motion Planning with Sliding Robots

Authors: Eduard Eiben, Robert Ganian, Iyad Kanj, and M. S. Ramanujan

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
We study a variant of the Coordinated Motion Planning problem on undirected graphs, referred to herein as the Coordinated Sliding-Motion Planning (CSMP) problem. In this variant, we are given an undirected graph G, k robots R₁,… ,R_k positioned on distinct vertices of G, p ≤ k distinct destination vertices for robots R₁,… ,R_p, and 𝓁 ∈ ℕ. The problem is to decide if there is a serial schedule of at most 𝓁 moves (i.e., of makespan 𝓁) such that at the end of the schedule each robot with a destination reaches it, where a robot’s move is a free path (unoccupied by any robots) from its current position to an unoccupied vertex. The problem is known to be NP-hard even on full grids. It has been studied in several contexts, including coin movement and reconfiguration problems, with respect to feasibility, complexity, and approximation. Geometric variants of the problem, in which congruent geometric-shape robots (e.g., unit disk/squares) slide or translate in the Euclidean plane, have also been studied extensively. We investigate the parameterized complexity of CSMP with respect to two parameters: the number k of robots and the makespan 𝓁. As our first result, we present a fixed-parameter algorithm for CSMP parameterized by k. For our second result, we present a fixed-parameter algorithm parameterized by 𝓁 for the special case of CSMP in which only a single robot has a destination and the graph is planar. A crucial new ingredient for both of our results is that the solution admits a succinct representation as a small labeled topological minor of the input graph.
Cite as

Eduard Eiben, Robert Ganian, Iyad Kanj, and M. S. Ramanujan. A Minor-Testing Approach for Coordinated Motion Planning with Sliding Robots. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 44:1-44:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{eiben_et_al:LIPIcs.SoCG.2025.44,
  author =	{Eiben, Eduard and Ganian, Robert and Kanj, Iyad and Ramanujan, M. S.},
  title =	{{A Minor-Testing Approach for Coordinated Motion Planning with Sliding Robots}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{44:1--44:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.44},
  URN =		{urn:nbn:de:0030-drops-231966},
  doi =		{10.4230/LIPIcs.SoCG.2025.44},
  annote =	{Keywords: coordinated motion planning on graphs, parameterized complexity, topological minor testing, planar graphs}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2024.29
Coordinated Motion Planning: Multi-Agent Path Finding in a Densely Packed, Bounded Domain

Authors: Sándor P. Fekete, Ramin Kosfeld, Peter Kramer, Jonas Neutzner, Christian Rieck, and Christian Scheffer

Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)

Abstract
We study Multi-Agent Path Finding for arrangements of labeled agents in the interior of a simply connected domain: Given a unique start and target position for each agent, the goal is to find a sequence of parallel, collision-free agent motions that minimizes the overall time (the makespan) until all agents have reached their respective targets. A natural case is that of a simply connected polygonal domain with axis-parallel boundaries and integer coordinates, i.e., a simple polyomino, which amounts to a simply connected union of lattice unit squares or cells. We focus on the particularly challenging setting of densely packed agents, i.e., one per cell, which strongly restricts the mobility of agents, and requires intricate coordination of motion. We provide a variety of novel results for this problem, including (1) a characterization of polyominoes in which a reconfiguration plan is guaranteed to exist; (2) a characterization of shape parameters that induce worst-case bounds on the makespan; (3) a suite of algorithms to achieve asymptotically worst-case optimal performance with respect to the achievable stretch for cases with severely limited maneuverability. This corresponds to bounding the ratio between obtained makespan and the lower bound provided by the max-min distance between the start and target position of any agent and our shape parameters. Our results extend findings by Demaine et al. [Erik D. Demaine et al., 2018; Erik D. Demaine et al., 2019] who investigated the problem for solid rectangular domains, and in the closely related field of Permutation Routing, as presented by Alpert et al. [H. Alpert et al., 2022] for convex pieces of grid graphs.
Cite as

Sándor P. Fekete, Ramin Kosfeld, Peter Kramer, Jonas Neutzner, Christian Rieck, and Christian Scheffer. Coordinated Motion Planning: Multi-Agent Path Finding in a Densely Packed, Bounded Domain. In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 29:1-29:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{fekete_et_al:LIPIcs.ISAAC.2024.29,
  author =	{Fekete, S\'{a}ndor P. and Kosfeld, Ramin and Kramer, Peter and Neutzner, Jonas and Rieck, Christian and Scheffer, Christian},
  title =	{{Coordinated Motion Planning: Multi-Agent Path Finding in a Densely Packed, Bounded Domain}},
  booktitle =	{35th International Symposium on Algorithms and Computation (ISAAC 2024)},
  pages =	{29:1--29:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-354-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{322},
  editor =	{Mestre, Juli\'{a}n and Wirth, Anthony},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.29},
  URN =		{urn:nbn:de:0030-drops-221565},
  doi =		{10.4230/LIPIcs.ISAAC.2024.29},
  annote =	{Keywords: multi-agent path finding, coordinated motion planning, bounded stretch, makespan, swarm robotics, reconfigurability, parallel sorting}
}
  • Refine by Type
  • 32 Document/PDF
  • 12 Document/HTML
  • 1 Artifact

  • Refine by Publication Year
  • 5 2026
  • 9 2025
  • 1 2024
  • 1 2023
  • 3 2022
  • Show More...

  • Refine by Author
  • 21 Scheffer, Christian
  • 20 Fekete, Sándor P.
  • 12 Rieck, Christian
  • 10 Keldenich, Phillip
  • 6 Kramer, Peter
  • Show More...

  • Refine by Series/Journal
  • 29 LIPIcs
  • 1 LITES
  • 2 TGDK

  • Refine by Classification
  • 20 Theory of computation → Computational geometry
  • 5 Computing methodologies → Motion path planning
  • 5 Theory of computation → Packing and covering problems
  • 1 Computing methodologies → Reasoning about belief and knowledge
  • 1 Computing methodologies → Semantic networks
  • Show More...

  • Refine by Keyword
  • 7 approximation
  • 6 makespan
  • 5 bounded stretch
  • 5 parallel motion
  • 5 swarm robotics
  • 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