Balanced Districting on Grid Graphs with Provable Compactness and Contiguity

Cyrus Hettle, Shixiang Zhu, Swati Gupta +1

Given a graph $G=(V,E)$ with vertex weights $w(v)$ and a desired number of parts $k$, the goal in graph partitioning problems is to partition the vertex set V into parts $V_1,\ld…