A Dynamic-Programming Heuristic for Regular Grid-Graph Partitioning

Abstract

Previous researchers have demonstrated that striping heuristics produce very good (and, in some cases, asymptotically optimal) partitions for regular grid graphs. These earlier methods differed in the domains of application and the stripe-height selection process, and did not have polynomial run-time guarantees. In this paper, we transform the stripe selection problem for general grid graphs into a shortest path problem. The running time for the entire process of transforming the problem and solving for the shortest path is polynomial with respect to the length of input for the original problem. Computational results are presented that demonstrate improved solution quality for general domains.