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 prove that efficient cycle-following based algorithms remain asymptotically optimal 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.