27 Search Results for "Scheffer, Christian"

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}
}
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}
}
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
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}
}
Document
DOI: 10.4230/LIPIcs.ESA.2023.45
The Lawn Mowing Problem: From Algebra to Algorithms

Authors: Sándor P. Fekete, Dominik Krupke, Michael Perk, Christian Rieck, and Christian Scheffer

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract
For a given polygonal region P, the Lawn Mowing Problem (LMP) asks for a shortest tour T that gets within Euclidean distance 1/2 of every point in P; this is equivalent to computing a shortest tour for a unit-diameter cutter C that covers all of P. As a generalization of the Traveling Salesman Problem, the LMP is NP-hard; unlike the discrete TSP, however, the LMP has defied efforts to achieve exact solutions, due to its combination of combinatorial complexity with continuous geometry. We provide a number of new contributions that provide insights into the involved difficulties, as well as positive results that enable both theoretical and practical progress. (1) We show that the LMP is algebraically hard: it is not solvable by radicals over the field of rationals, even for the simple case in which P is a 2×2 square. This implies that it is impossible to compute exact optimal solutions under models of computation that rely on elementary arithmetic operations and the extraction of kth roots, and explains the perceived practical difficulty. (2) We exploit this algebraic analysis for the natural class of polygons with axis-parallel edges and integer vertices (i.e., polyominoes), highlighting the relevance of turn-cost minimization for Lawn Mowing tours, and leading to a general construction method for feasible tours. (3) We show that this construction method achieves theoretical worst-case guarantees that improve previous approximation factors for polyominoes. (4) We demonstrate the practical usefulness beyond polyominoes by performing an extensive practical study on a spectrum of more general benchmark polygons: We obtain solutions that are better than the previous best values by Fekete et al., for instance sizes up to 20 times larger.
Cite as

Sándor P. Fekete, Dominik Krupke, Michael Perk, Christian Rieck, and Christian Scheffer. The Lawn Mowing Problem: From Algebra to Algorithms. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 45:1-45:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{fekete_et_al:LIPIcs.ESA.2023.45,
  author =	{Fekete, S\'{a}ndor P. and Krupke, Dominik and Perk, Michael and Rieck, Christian and Scheffer, Christian},
  title =	{{The Lawn Mowing Problem: From Algebra to Algorithms}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{45:1--45:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. 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.2023.45},
  URN =		{urn:nbn:de:0030-drops-186985},
  doi =		{10.4230/LIPIcs.ESA.2023.45},
  annote =	{Keywords: Geometric optimization, covering problems, tour problems, lawn mowing, algebraic hardness, approximation algorithms, algorithm engineering}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2022.17
Efficiently Reconfiguring a Connected Swarm of Labeled Robots

Authors: Sándor P. Fekete, Peter Kramer, Christian Rieck, Christian Scheffer, and Arne Schmidt

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract
When considering motion planning for a swarm of n labeled robots, we need to rearrange a given start configuration into a desired target configuration via a sequence of parallel, continuous, collision-free robot motions. The objective is to reach the new configuration in a minimum amount of time; an important constraint is to keep the swarm connected at all times. Problems of this type have been considered before, with recent notable results achieving constant stretch for not necessarily connected reconfiguration: If mapping the start configuration to the target configuration requires a maximum Manhattan distance of d, the total duration of an overall schedule can be bounded to 𝒪(d), which is optimal up to constant factors. However, constant stretch could only be achieved if disconnected reconfiguration is allowed, or for scaled configurations (which arise by increasing all dimensions of a given object by the same multiplicative factor) of unlabeled robots. We resolve these major open problems by (1) establishing a lower bound of Ω(√n) for connected, labeled reconfiguration and, most importantly, by (2) proving that for scaled arrangements, constant stretch for connected reconfiguration can be achieved. In addition, we show that (3) it is NP-hard to decide whether a makespan of 2 can be achieved, while it is possible to check in polynomial time whether a makespan of 1 can be achieved.
Cite as

Sándor P. Fekete, Peter Kramer, Christian Rieck, Christian Scheffer, and Arne Schmidt. Efficiently Reconfiguring a Connected Swarm of Labeled Robots. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 17:1-17:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{fekete_et_al:LIPIcs.ISAAC.2022.17,
  author =	{Fekete, S\'{a}ndor P. and Kramer, Peter and Rieck, Christian and Scheffer, Christian and Schmidt, Arne},
  title =	{{Efficiently Reconfiguring a Connected Swarm of Labeled Robots}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{17:1--17:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.17},
  URN =		{urn:nbn:de:0030-drops-173028},
  doi =		{10.4230/LIPIcs.ISAAC.2022.17},
  annote =	{Keywords: Motion planning, parallel motion, bounded stretch, makespan, connectivity, swarm robotics}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2022.67
The Dispersive Art Gallery Problem

Authors: Christian Rieck and Christian Scheffer

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract
We introduce a new variant of the art gallery problem that comes from safety issues. In this variant we are not interested in guard sets of smallest cardinality, but in guard sets with largest possible distances between these guards. To the best of our knowledge, this variant has not been considered before. We call it the Dispersive Art Gallery Problem. In particular, in the dispersive art gallery problem we are given a polygon 𝒫 and a real number 𝓁, and want to decide whether 𝒫 has a guard set such that every pair of guards in this set is at least a distance of 𝓁 apart. In this paper, we study the vertex guard variant of this problem for the class of polyominoes. We consider rectangular visibility and distances as geodesics in the L₁-metric. Our results are as follows. We give a (simple) thin polyomino such that every guard set has minimum pairwise distances of at most 3. On the positive side, we describe an algorithm that computes guard sets for simple polyominoes that match this upper bound, i.e., the algorithm constructs worst-case optimal solutions. We also study the computational complexity of computing guard sets that maximize the smallest distance between all pairs of guards within the guard sets. We prove that deciding whether there exists a guard set realizing a minimum pairwise distance for all pairs of guards of at least 5 in a given polyomino is NP-complete. We were also able to find an optimal dynamic programming approach that computes a guard set that maximizes the minimum pairwise distance between guards in tree-shaped polyominoes, i.e., computes optimal solutions; due to space constraints, details can be found in the full version of our paper [Christian Rieck and Christian Scheffer, 2022]. Because the shapes constructed in the NP-hardness reduction are thin as well (but have holes), this result completes the case for thin polyominoes.
Cite as

Christian Rieck and Christian Scheffer. The Dispersive Art Gallery Problem. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 67:1-67:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{rieck_et_al:LIPIcs.ISAAC.2022.67,
  author =	{Rieck, Christian and Scheffer, Christian},
  title =	{{The Dispersive Art Gallery Problem}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{67:1--67:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.67},
  URN =		{urn:nbn:de:0030-drops-173522},
  doi =		{10.4230/LIPIcs.ISAAC.2022.67},
  annote =	{Keywords: Art gallery, dispersion, polyominoes, NP-completeness, r-visibility, vertex guards, L₁-metric, worst-case optimal}
}
Document
Media Exposition
DOI: 10.4230/LIPIcs.SoCG.2022.65
Space Ants: Episode II - Coordinating Connected Catoms (Media Exposition)

Authors: Julien Bourgeois, Sándor P. Fekete, Ramin Kosfeld, Peter Kramer, Benoît Piranda, Christian Rieck, and Christian Scheffer

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)

Abstract
How can a set of identical mobile agents coordinate their motions to transform their arrangement from a given starting to a desired goal configuration? We consider this question in the context of actual physical devices called Catoms, which can perform reconfiguration, but need to maintain connectivity at all times to ensure communication and energy supply. We demonstrate and animate algorithmic results, in particular a proof of hardness, as well as an algorithm that guarantees constant stretch for certain classes of arrangements: If mapping the start configuration to the target configuration requires a maximum Manhattan distance of d, then the total duration of our overall schedule is in 𝒪(d), which is optimal up to constant factors.
Cite as

Julien Bourgeois, Sándor P. Fekete, Ramin Kosfeld, Peter Kramer, Benoît Piranda, Christian Rieck, and Christian Scheffer. Space Ants: Episode II - Coordinating Connected Catoms (Media Exposition). In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 65:1-65:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bourgeois_et_al:LIPIcs.SoCG.2022.65,
  author =	{Bourgeois, Julien and Fekete, S\'{a}ndor P. and Kosfeld, Ramin and Kramer, Peter and Piranda, Beno\^{i}t and Rieck, Christian and Scheffer, Christian},
  title =	{{Space Ants: Episode II - Coordinating Connected Catoms}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{65:1--65:6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.65},
  URN =		{urn:nbn:de:0030-drops-160732},
  doi =		{10.4230/LIPIcs.SoCG.2022.65},
  annote =	{Keywords: Motion planning, parallel motion, bounded stretch, scaled shape, makespan, connectivity, swarm robotics}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2021.9
Connected Coordinated Motion Planning with Bounded Stretch

Authors: Sándor P. Fekete, Phillip Keldenich, Ramin Kosfeld, Christian Rieck, and Christian Scheffer

Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)

Abstract
We consider the problem of coordinated motion planning for a swarm of simple, identical robots: From a given start grid configuration of robots, we need to reach a desired target configuration via a sequence of parallel, continuous, collision-free robot motions, such that the set of robots induces a connected grid graph at all integer times. The objective is to minimize the makespan of the motion schedule, i.e., to reach the new configuration in a minimum amount of time. We show that this problem is NP-hard, even for deciding whether a makespan of 2 can be achieved, while it is possible to check in polynomial time whether a makespan of 1 can be achieved. On the algorithmic side, we establish simultaneous constant-factor approximation for two fundamental parameters, by achieving constant stretch for constant scale. Scaled shapes (which arise by increasing all dimensions of a given object by the same multiplicative factor) have been considered in previous seminal work on self-assembly, often with unbounded or logarithmic scale factors; we provide methods for a generalized scale factor, bounded by a constant. Moreover, our algorithm achieves a constant stretch factor: If mapping the start configuration to the target configuration requires a maximum Manhattan distance of d, then the total duration of our overall schedule is 𝒪(d), which is optimal up to constant factors.
Cite as

Sándor P. Fekete, Phillip Keldenich, Ramin Kosfeld, Christian Rieck, and Christian Scheffer. Connected Coordinated Motion Planning with Bounded Stretch. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 9:1-9:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{fekete_et_al:LIPIcs.ISAAC.2021.9,
  author =	{Fekete, S\'{a}ndor P. and Keldenich, Phillip and Kosfeld, Ramin and Rieck, Christian and Scheffer, Christian},
  title =	{{Connected Coordinated Motion Planning with Bounded Stretch}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{9:1--9:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.9},
  URN =		{urn:nbn:de:0030-drops-154423},
  doi =		{10.4230/LIPIcs.ISAAC.2021.9},
  annote =	{Keywords: Motion planning, parallel motion, bounded stretch, scaled shape, makespan, connectivity, swarm robotics}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2021.36
Packing Squares into a Disk with Optimal Worst-Case Density

Authors: Sándor P. Fekete, Vijaykrishna Gurunathan, Kushagra Juneja, Phillip Keldenich, Linda Kleist, and Christian Scheffer

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)

Abstract
We provide a tight result for a fundamental problem arising from packing squares into a circular container: The critical density of packing squares into a disk is δ = 8/(5π)≈ 0.509. This implies that any set of (not necessarily equal) squares of total area A ≤ 8/5 can always be packed into a disk with radius 1; in contrast, for any ε > 0 there are sets of squares of total area 8/5+ε that cannot be packed, even if squares may be rotated. This settles the last (and arguably, most elusive) case of packing circular or square objects into a circular or square container: The critical densities for squares in a square (1/2), circles in a square (π/(3+2√2) ≈ 0.539) and circles in a circle (1/2) have already been established, making use of recursive subdivisions of a square container into pieces bounded by straight lines, or the ability to use recursive arguments based on similarity of objects and container; neither of these approaches can be applied when packing squares into a circular container. Our proof uses a careful manual analysis, complemented by a computer-assisted part that is based on interval arithmetic. Beyond the basic mathematical importance, our result is also useful as a blackbox lemma for the analysis of recursive packing algorithms. At the same time, our approach showcases the power of a general framework for computer-assisted proofs, based on interval arithmetic.
Cite as

Sándor P. Fekete, Vijaykrishna Gurunathan, Kushagra Juneja, Phillip Keldenich, Linda Kleist, and Christian Scheffer. Packing Squares into a Disk with Optimal Worst-Case Density. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 36:1-36:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{fekete_et_al:LIPIcs.SoCG.2021.36,
  author =	{Fekete, S\'{a}ndor P. and Gurunathan, Vijaykrishna and Juneja, Kushagra and Keldenich, Phillip and Kleist, Linda and Scheffer, Christian},
  title =	{{Packing Squares into a Disk with Optimal Worst-Case Density}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{36:1--36:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.36},
  URN =		{urn:nbn:de:0030-drops-138356},
  doi =		{10.4230/LIPIcs.SoCG.2021.36},
  annote =	{Keywords: Square packing, packing density, tight worst-case bound, interval arithmetic, approximation}
}
  • Refine by Type
  • 26 Document/PDF
  • 6 Document/HTML
  • 1 Artifact

  • Refine by Publication Year
  • 8 2025
  • 1 2024
  • 1 2023
  • 3 2022
  • 2 2021
  • Show More...

  • Refine by Author
  • 20 Scheffer, Christian
  • 18 Fekete, Sándor P.
  • 11 Rieck, Christian
  • 10 Keldenich, Phillip
  • 5 Kramer, Peter
  • Show More...

  • Refine by Series/Journal
  • 24 LIPIcs
  • 1 LITES
  • 1 TGDK

  • Refine by Classification
  • 16 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 Hardware → Chip-level power issues
  • 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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact