5 papers
FO Value Discovery and Partial Vertex Cover Discovery
Enna Gerhard, Stephanie Maaz, Pascale Schott +2
We study solution discovery in the token-sliding model from a logical and cost-value optimization perspective. In solution discovery, we are given a graph, an initial placement of…
Separating Feasibility and Movement in Solution Discovery: The Case of Path Discovery
Hanno von Bergen, Larissa Fastenau, Enna Gerhard +8
We study solution discovery, where the goal is to obtain a feasible solution to a problem from an initial configuration by a bounded sequence of local moves. In many applications,…
On Algorithmic Meta-Theorems for Solution Discovery: Tractability and Barriers
Nicolas Bousquet, Amer E. Mouawad, Stephanie Maaz +2
Solution discovery asks whether a given (infeasible) starting configuration to a problem can be transformed into a feasible solution using a limited number of transformation steps.…
Efficient algorithms to solve atom reconfiguration problems. II. The assignment-rerouting-ordering (aro) algorithm
Remy El Sabeh, Jessica Bohm, Zhiqian Ding +5
Programmable arrays of optical traps enable the assembly of configurations of single atoms to perform controlled experiments on quantum many-body systems. Finding the sequence of c…
Efficient algorithms to solve atom reconfiguration problems. I. The redistribution-reconfiguration (red-rec) algorithm
Barry Cimring, Remy El Sabeh, Marc Bacvanski +5
We propose the redistribution-reconfiguration (red-rec) algorithm to prepare large configurations of atoms using arrays of dynamic optical traps. Red-rec exploits simple heuristics…