Sandor P. Fekete

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. [18, 19] who investigated the problem for solid rectangular domains, and in the closely related field of Permutation Routing , as presented by Alpert et al. [10] for convex pieces of grid graphs.

We present significant progress for scalable and fine-grained computation of large flooding events. As a first step, we describe (I) breakthroughs for simulating time-dependent, high-resolution runoff in large-scale heavy-rain scenarios, based on two algorithmic speedup techniques. The first is (a) a flow-based subdivision technique of the terrain that enables independent, parallel simulation of different regions, while ensuring consistency of the overall simulation. The second is (b) a feature-based algorithmic grid refinement technique. Using this refinement, runtimes for high-resolution hydrodynamic simulations are reduced by 85–90% compared to uniform 1m grids, which can result in better than real-time performance for realistic inputs in medium-sized regions. In combination with state-of-the-art commercial software and powerful computing devices, these techniques make it possible to carry out simulations for large-scale scenarios that were previously infeasible due to memory requirements, and provide considerable speedup for medium- or small-scale scenarios. Combining both techniques, the time-dependent runoff during a five-hour heavy-rain event at 1 m output resolution for an area of 370 km² in the mountainous Harz region (i.e., for 370,000,000 terrain points with considerable elevation differences and ensuing dynamic flows) can be simulated within three days; without our techniques, such a simulation would not even be possible due to the unmanageable memory requirements. This progress enables us to demonstrate how to address a second challenge: How can we deal with the instability of precipitation events, which are notoriously difficult to predict with good accuracy? We use our new computational capabilities to conduct (II) a large-scale, multifaceted sensitivity analysis, providing insights into different scenarios for possible time-dependent runoff and flooding when varying the input precipitation for our study area. This makes it possible to identify both regions of stability (for which the outcomes are largely unchanged under input variations) as well as critically unstable locations (for which the outcome may change significantly under input variations). In particular the latter is of crucial value for effective disaster mitigation: Knowing where relatively small changes in the input can make a huge difference in the outcome is invaluable when deciding where to invest limited resources with the greatest impact. We demonstrate the viability of this approach by identifying such a critical location for our study area.

We present significant progress for scalable and fine-grained computation of large flooding events. As a first step, we describe (I) breakthroughs for simulating time-dependent, high-resolution runoff in large-scale heavy-rain scenarios, based on two algorithmic speedup techniques. The first is (a) a flow-based subdivision technique of the terrain that enables independent, parallel simulation of different regions, while ensuring consistency of the overall simulation. The second is (b) a feature-based algorithmic grid refinement technique. Using this refinement, runtimes for high-resolution hydrodynamic simulations are reduced by 85–90% compared to uniform 1m grids, which can result in better than real-time performance for realistic inputs in medium-sized regions. In combination with state-of-the-art commercial software and powerful computing devices, these techniques make it possible to carry out simulations for large-scale scenarios that were previously infeasible due to memory requirements, and provide considerable speedup for medium- or small-scale scenarios. Combining both techniques, the time-dependent runoff during a five-hour heavy-rain event at 1 m output resolution for an area of 370 km² in the mountainous Harz region (i.e., for 370,000,000 terrain points with considerable elevation differences and ensuing dynamic flows) can be simulated within three days; without our techniques, such a simulation would not even be possible due to the unmanageable memory requirements. This progress enables us to demonstrate how to address a second challenge: How can we deal with the instability of precipitation events, which are notoriously difficult to predict with good accuracy? We use our new computational capabilities to conduct (II) a large-scale, multifaceted sensitivity analysis, providing insights into different scenarios for possible time-dependent runoff and flooding when varying the input precipitation for our study area. This makes it possible to identify both regions of stability (for which the outcomes are largely unchanged under input variations) as well as critically unstable locations (for which the outcome may change significantly under input variations). In particular the latter is of crucial value for effective disaster mitigation: Knowing where relatively small changes in the input can make a huge difference in the outcome is invaluable when deciding where to invest limited resources with the greatest impact. We demonstrate the viability of this approach by identifying such a critical location for our study area.

We present significant progress for scalable and fine-grained computation of large flooding events. As a first step, we describe (I) breakthroughs for simulating time-dependent, high-resolution runoff in large-scale heavy-rain scenarios, based on two algorithmic speedup techniques. The first is (a) a flow-based subdivision technique of the terrain that enables independent, parallel simulation of different regions, while ensuring consistency of the overall simulation. The second is (b) a feature-based algorithmic grid refinement technique. Using this refinement, runtimes for high-resolution hydrodynamic simulations are reduced by 85–90% compared to uniform 1m grids, which can result in better than real-time performance for realistic inputs in medium-sized regions. In combination with state-of-the-art commercial software and powerful computing devices, these techniques make it possible to carry out simulations for large-scale scenarios that were previously infeasible due to memory requirements, and provide considerable speedup for medium- or small-scale scenarios. Combining both techniques, the time-dependent runoff during a five-hour heavy-rain event at 1 m output resolution for an area of 370 km² in the mountainous Harz region (i.e., for 370,000,000 terrain points with considerable elevation differences and ensuing dynamic flows) can be simulated within three days; without our techniques, such a simulation would not even be possible due to the unmanageable memory requirements. This progress enables us to demonstrate how to address a second challenge: How can we deal with the instability of precipitation events, which are notoriously difficult to predict with good accuracy? We use our new computational capabilities to conduct (II) a large-scale, multifaceted sensitivity analysis, providing insights into different scenarios for possible time-dependent runoff and flooding when varying the input precipitation for our study area. This makes it possible to identify both regions of stability (for which the outcomes are largely unchanged under input variations) as well as critically unstable locations (for which the outcome may change significantly under input variations). In particular the latter is of crucial value for effective disaster mitigation: Knowing where relatively small changes in the input can make a huge difference in the outcome is invaluable when deciding where to invest limited resources with the greatest impact. We demonstrate the viability of this approach by identifying such a critical location for our study area.

We implement and evaluate different methods for the reconfiguration of a connected arrangement of tiles into a desired target shape, using a single active robot that can move along the tile structure. This robot can pick up, carry, or drop off one tile at a time, but it must maintain a single connected configuration at all times. Becker et al. (CCCG 2025) recently proposed an algorithm that uses histograms as canonical intermediate configurations, guaranteeing performance within a constant factor of the optimal solution if the start and target configuration are well-separated. We implement and evaluate this algorithm, both in a simulated and practical setting, using an inchworm type robot to compare it with two existing heuristic algorithms.

Modern software systems are typically configurable, a fundamental prerequisite for wide applicability and reusability. This flexibility poses an extraordinary challenge for quality assurance, as the enormous number of possible configurations makes it impractical to test each of them separately. This is where t-wise interaction sampling can be used to systematically cover the configuration space and detect unknown feature interactions. Over the last two decades, numerous algorithms for computing small interaction samples have been studied, providing improvements for a range of heuristic results; nevertheless, it has remained unclear how much these results can still be improved. We present a significant breakthrough: a fundamental framework, based on the mathematical principle of duality, for combining near-optimal solutions with provable lower bounds on the required sample size. This implies that we no longer need to work on heuristics with marginal or no improvement, but can certify the solution quality by establishing a limit on the remaining gap; in many cases, we can even prove optimality of achieved solutions. This theoretical contribution also provides extensive practical improvements: Our algorithm SampLNS was tested on 47 small and medium-sized configurable systems from the existing literature. SampLNS can reliably find samples of smaller size than previous methods in 85% of the cases; moreover, we can achieve and prove optimality of solutions for 63% of all instances. This makes it possible to avoid cumbersome efforts of minimizing samples by researchers as well as practitioners, and substantially save testing resources for most configurable systems.

We investigate several geometric problems of finding tours and cycle covers with minimum turn cost, which have been studied in the past, with complexity, approximation results, and open problems dating back to work by Arkin et al. in 2001. Many new practical applications have spawned variants: For full coverage, all points have to be covered, for subset coverage, specific points have to be covered, and for penalty coverage, points may be left uncovered by incurring a penalty. We show that finding a minimum-turn (full) cycle cover is NP-hard even in 2-dimensional grid graphs, solving the long-standing open Problem 53 in The Open Problems Project edited by Demaine, Mitchell and O’Rourke. We also prove NP-hardness of finding a subset cycle cover of minimum turn cost in thin grid graphs, for which Arkin et al. gave a polynomial-time algorithm for full coverage; this shows that their boundary techniques cannot be applied to compute exact solutions for subset and penalty variants. We also provide a number of positive results. In particular, we establish the first constant-factor approximation algorithms for all considered subset and penalty problem variants for grid-based instances, based on LP/IP techniques. These geometric versions allow many possible edge directions (and thus, turn angles, such as in hexagonal grids or higher-dimensional variants); our approximation factors improve the combinatorial ones of Arkin et al.