The goal of this project was to evaluate the distance between Kornhauser’s algorithm for the Pebble Motion Problem on graphs and the optimal solution — specifically, by comparing the number of moves required by each method to transform an initial configuration into a target configuration. Kornhauser’s algorithm offers a general polynomial-time solution based on group theory, decomposing permutations into 3-cycles. In contrast, we implemented an optimal solution using Mixed-Integer Linear Programming (MILP), which explicitly minimizes the total number of moves.
We developed a MATLAB simulation environment and conducted a series of experiments on graphs of varying sizes and random configurations. Our results show that although Kornhauser’s algorithm always produces a valid solution, it often requires significantly more moves than the MILP-based optimal method — especially on larger graphs or with complex permutations. This allowed us to quantify the algorithmic “distance” from optimality and better understand the trade-offs between general efficiency and minimality.