×

zbMATH — the first resource for mathematics

Geometry of graph partitions via optimal transport. (English) Zbl 07271898
MSC:
65K10 Numerical optimization and variational techniques
90B06 Transportation, logistics and supply chain management
05C21 Flows in graphs
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network Flows, Prentice-Hall, Englewood Cliffs, NJ, 1988. · Zbl 1201.90001
[2] S. Bangia, C. V. Graves, G. Herschlag, H. S. Kang, J. Luo, J. C. Mattingly, and R. Ravier, Redistricting: Drawing the Line, preprint, arXiv:1704.03360, 2017.
[3] M. Beckmann, A continuous model of transportation, Econometrica, 20 (1952), pp. 643-660. · Zbl 0048.13001
[4] I. Borg, P. J. Groenen, and P. Mair, Applied Multidimensional Scaling, Springer Science & Business Media, New York, 2012. · Zbl 1416.62017
[5] L. A. Caffarelli and R. J. McCann, Free boundaries in optimal transport and Monge-Ampère obstacle problems, Ann. of Math. (2), 171 (2010), pp. 673-730. · Zbl 1196.35231
[6] J. Chen and J. Rodden, Cutting through the thicket: Redistricting simulations and the detection of partisan gerrymanders, Election Law J., 14 (2015), pp. 331-345.
[7] J. Chen and J. Rodden, Unintentional gerrymandering: Political geography and electoral bias in legislatures, Quart. J. Political Sci., 8 (2013), pp. 239-269.
[8] M. Chikina, A. Frieze, and W. Pegden, Assessing significance in a Markov chain without mixing, Proc. Natl. Acad. Sci. USA, 114 (2017), pp. 2860-2864. · Zbl 1407.62302
[9] L. Chizat, G. Peyré, B. Schmitzer, and F.-X. Vialard, Scaling algorithms for unbalanced optimal transport problems, Math. Comp., 87 (2018), pp. 2563-2609. · Zbl 1402.90120
[10] L. Chizat, G. Peyré, B. Schmitzer, and F.-X. Vialard, Unbalanced optimal transport: Dynamic and Kantorovich formulations, J. Funct. Anal., 274 (2018), pp. 3090-3123. · Zbl 1387.49066
[11] M. Cuturi and D. Avis, Ground metric learning, J. Mach. Learn. Res., 15 (2014), pp. 533-564. · Zbl 1317.68149
[12] W. H. Day, The complexity of computing metric distances between partitions, Math. Social Sci., 1 (1981), pp. 269-287. · Zbl 0497.62049
[13] D. DeFord and M. Duchin, Redistricting reform in Virginia: Districting criteria in context, Virginia Policy Rev., 12 (2019), pp. 120-146.
[14] D. DeFord, M. Duchin, and J. Solomon, Recombination: A Family of Markov Chains for Redistricting, submitted, arXiv:1911.05725, 2019.
[15] L. Denøeud and A. Guénoche, Comparison of distance indices between partitions, in Data Science and Classification, Springer-Verlag, Berlin, 2006, pp. 21-28.
[16] S. Diamond and S. Boyd, CVXPY: A Python-embedded modeling language for convex optimization, J. Mach. Learn. Res., 17 (2016), pp. 1-5. · Zbl 1360.90008
[17] M. Essid and J. Solomon, Quadratically regularized optimal transport on graphs, SIAM J. Sci. Comput., 40 (2018), pp. A1961-A1986. · Zbl 1394.65041
[18] A. Figalli and N. Gigli, A new transportation distance between non-negative measures, with applications to gradients flows with Dirichlet boundary conditions, J. Math. Pures Appl. (9), 94 (2010), pp. 107-130. · Zbl 1203.35126
[19] A. Galichon, Optimal Transport Methods in Economics, Princeton University Press, Princeton, NJ, 2018.
[20] N. Guillen, C. Mou, and A. Świȩch, Coupling Lévy measures and comparison principles for viscosity solutions, Trans. Amer. Math. Soc., 372 (2019), pp. 7327-7370. · Zbl 1428.35080
[21] G. Herschlag, gjh/districtingdatarepository, September 2019, http://git.math.duke.edu/gitlab/gjh/districtingDataRepository.
[22] G. Herschlag, H. S. Kang, J. Luo, C. V. Graves, S. Bangia, R. Ravier, and J. C. Mattingly, Quantifying Gerrymandering in North Carolina, Statist. Public Ploicy, 7 (2020), pp. 30-38.
[23] G. Herschlag, R. Ravier, and J. C. Mattingly, Evaluating Partisan Gerrymandering in Wisconsin, preprint, arXiv:1709.01596, 2017.
[24] L. V. Kantorovich, On the translocation of masses, in Dokl. Akad. Nauk., 37 (1942), pp. 199-201. · Zbl 0061.09705
[25] G. P. Leonardi and I. Tamanini, Metric spaces of partitions, and Caccioppoli partitions, Adv. Math. Sci. Appl., 12 (2002), pp. 725-753. · Zbl 1044.49030
[26] D. Lombardi and E. Maitre, Eulerian models and algorithms for unbalanced optimal transport, ESAIM Math. Model. Numer. Anal., 49 (2015), pp. 1717-1744. · Zbl 1334.65112
[27] S. Manson, J. Schroeder, D. Van Riper, T. Kugler, and S. Ruggles, IPUMS National Historical Geographic Information System: Version 12.0 [database], University of Minnesota, Minneapolis, MN, 2017.
[28] M. Meilă, Comparing clusterings-an information based distance, J. Multivariate Anal., 98 (2007), pp. 873-895. · Zbl 1298.91124
[29] Metric Geometry and Gerrymandering Group, mggg/gerrychain: v\textup0.2.12, July 2019, https://github.com/mggg/gerrychain.
[30] Metric Geometry and Gerrymandering Group and R. Buck, mggg-states, September 2019, https://github.com/mggg-states.
[31] G. Monge, Mémoire sur la théorie des déblais et des remblais, Histoire de l’Académie Royale des Sciences de Paris, 1781.
[32] L. Najt, D. DeFord, and J. Solomon, Complexity and Geometry of Sampling Connected Graph Partitions, preprint, arXiv:1908.08881, 2019.
[33] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay, Scikit-learn: Machine learning in Python, J. Mach. Learn., 12 (2011), pp. 2825-2830. · Zbl 1280.68189
[34] G. Peyré and M. Cuturi, Computational optimal transport, Found. Trends Mach. Learn., 11 (2019), pp. 355-607. · Zbl 07039357
[35] F. Santambrogio, Prescribed-divergence problems in optimal transportation, lecture notes presented at the Mathemetical Sciences Research Institute, 2013
[36] F. Santambrogio, Optimal Transport for Applied Mathematicians, Springer, Cham, 2015. · Zbl 1401.49002
[37] Z. Schutzman, zschutzman/enumerator: v0.1.5, 10 2019, https://github.com/zschutzman/enumerator.
[38] L. Slater Morton, Lagrange Multipliers Revisited, Cowles Commission Discussion Paper: Mathematics 403, Yale University, New Haven, CT, 1950.
[39] C. Villani, Topics in Optimal Transportation, Grad. Stud. Math. 58, American Mathematical Society, Providence, RI, 2003. · Zbl 1106.90001
[40] H. P. Young, Measuring the compactness of legislative districts, Legislative Stud. Quart., 13 (1988), pp. 105-115.
[41] M. Yurochkin, S. Claici, E. Chien, F. Mirzazadeh, and J. Solomon, Hierarchical optimal transport for document representation, in Proceedings of the Neural Information Processing Systems Conference, 2019.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.