Before revision:  Despite their NP-hardness, we are able to again develop efficient algorithms for 2D fully and partially labeled settingsthat are asymptotically optimal , in expectation, assuming that the initial configuration is randomly selected . Simulation studies confirm the effectiveness of our algorithms in comparison to natural greedy best-first algorithms.
After revision:  Despite their NP-hardness, we are able to again develop efficient algorithms for 2D fully and partially labeled settingsthat are asymptotically optimal , in expectation, using the interesting fact that random permutations induce only a small number of cycles. We further improve these algorithms to provide 1.x-optimality when the number of items is small . Simulation studies confirm the effectiveness of our algorithms in comparison to natural greedy best-first algorithms.