Geometry of Graph Partitions via Optimal Transport

DOI10.1137/19M1295258zbMath1452.65107arXiv1910.09618OpenAlexW3094265067MaRDI QIDQ5132020

Parker Rule, Justin Solomon, Zachary Schutzman, Thomas Weighill, Nestor Guillen, Tara Abrishami, Si Wu

Publication date: 9 November 2020

Published in: SIAM Journal on Scientific Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1910.09618

zbMATH Keywords

convex optimizationnetwork flowsoptimal transport

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Numerical optimization and variational techniques (65K10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Flows in graphs (05C21) Optimal transportation (49Q22)

Related Items (5)

Geometric Averages of Partitioned Datasets ⋮ Three applications of entropy to gerrymandering ⋮ The (homological) persistence of gerrymandering ⋮ Reconfiguration of connected graph partitions via recombination ⋮ Reconfiguration of connected graph partitions via recombination

Uses Software

• Scikit
• CVXPY
• GitHub
• enumerator
• GerryChain

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computational Optimal Transport: With Applications to Data Science
• Free boundaries in optimal transport and Monge-Ampère obstacle problems
• A new transportation distance between non-negative measures, with applications to gradients flows with Dirichlet boundary conditions
• The complexity of computing metric distances between partitions
• Unbalanced optimal transport: dynamic and Kantorovich formulations
• Applied multidimensional scaling
• Optimal transport for applied mathematicians. Calculus of variations, PDEs, and modeling
• Comparing clusterings -- an information based distance
• CVXPY: A Python-Embedded Modeling Language for Convex Optimization
• Quadratically Regularized Optimal Transport on Graphs
• Scaling algorithms for unbalanced optimal transport problems
• Eulerian models and algorithms for unbalanced optimal transport
• Assessing significance in a Markov chain without mixing
• Coupling Lévy measures and comparison principles for viscosity solutions
• A Continuous Model of Transportation

This page was built for publication: Geometry of Graph Partitions via Optimal Transport