2019/10/21 by Tara Abrishami, Abrishami, Tara, Nestor Guillen +11 · 1 citation
Computer Science · Economics, Econometrics and Finance · Engineering · Mathematics · #Advanced Graph Theory Research #Algorithm #Combinatorics #Computer science #Computers and Society (cs.CY) #Data Management and Algorithms #Discrete Mathematics (cs.DM) #Engineering #FOS: Computer and information sciences #FOS: Mathematics #Game Theory and Voting Systems #Graph #Graph partition #Linear programming #Mathematical optimization #Mathematics #Metric (unit) #Optimization and Control (math.OC) #Pairwise comparison #Partition (number theory) #Statistics #cs.CY #cs.DM #math.OC
paper · pdf · doi:10.48550/arxiv.1910.09618
30 pages, 15 figures
arxiv created 2019/10/21 · openalex publication_date 2019/10/21 · arxiv updated 2019/10/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
We define a distance metric between partitions of a graph using machinery from optimal transport. Our metric is built from a linear assignment problem that matches partition components, with assignment cost proportional to transport distance over graph edges. We show that our distance can be computed using a single linear program without precomputing pairwise assignment costs and derive several theoretical properties of the metric. Finally, we provide experiments demonstrating these properties empirically, specifically focusing on its value for new problems in ensemble-based analysis of political districting plans.