On Computing Makespan-Optimal Solutions for Generalized Sliding-Tile Puzzles
Authors: Marcus Gozon, Jingjin Yu
AAAI 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We establish that computing makespan-optimal solutions for GSTP is NP-complete and developing polynomial time algorithms yielding makespans approximating the minimum with expected/high probability constant factors, assuming randomized start and goal configurations. We establish tighter makespan lower bounds for GSTP for all possible numbers of escorts. We establish tighter makespan upper bounds for GSTP for all possible numbers of escorts that match the corresponding makespan lower bounds, asymptotically, thus closing the makespan optimality gap for GSTP. |
| Researcher Affiliation | Academia | 1University of Michigan 2Rutgers University mgozon@umich.edu, jingjin.yu@cs.rutgers.edu |
| Pseudocode | No | No explicit pseudocode or algorithm blocks were found. Algorithms are described textually. |
| Open Source Code | No | The paper does not provide any explicit statements or links about open-source code for the described methodology. |
| Open Datasets | No | This is a theoretical paper and does not use datasets for training or evaluation in the empirical sense. It refers to 'randomized start and goal configurations' for theoretical analysis. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments with dataset splits for training, validation, or testing. |
| Hardware Specification | No | No specific hardware details (e.g., GPU/CPU models, memory specifications) used for running experiments or computations are mentioned in the paper. |
| Software Dependencies | No | The paper does not provide any specific software dependencies or version numbers. |
| Experiment Setup | No | The paper is theoretical and does not involve empirical experiments, thus no experimental setup details like hyperparameters or training configurations are provided. |