Research

Publications

• A mass transportation method of domain decomposition for multi-agent teams with heterogeneous coverage capabilities with Sean Maxon, Qiuyang Tao, and Fumin Zang of the Georgia Institute of Technology. In preparation.

Abstract. We propose a mass transport method that decomposes the coverage region in a nonhierarchical manner that is nearly optimal with respect to some user-defined cost function. This method does not rely on any nonlocal information, giving it effectively constant scaling behavior, making it ideal for large swarms. It dynamically adapts to changing conditions and guarantees full region coverage, even when agents are removed from or added to a team. In support of the method, we share simulation and live-test UAV results.

• A real‐valued auction algorithm for optimal transport with Luca Dieci of the Georgia Institute of Technology. Statistical Analysis and Data Mining. 12: 514-533. November 2019. http://doi.org/10.1002/sam.11443

Abstract. Optimal transportation theory is an area of mathematics with real‐world applications in fields ranging from economics to optimal control to machine learning. We propose a new algorithm for solving discrete transport (network flow) problems, based on classical auction methods. Auction methods were originally developed as an alternative to the Hungarian method for the assignment problem, so the classic auction‐based algorithms solve integer‐valued optimal transport by converting such problems into assignment problems. The general transport auction method we propose works directly on real‐valued transport problems. Our results prove termination, bound the transport error, and relate our algorithm to the classic algorithms of Bertsekas and Castañón.

• The boundary method for semi-discrete optimal transport partitions and Wasserstein distance computation with Luca Dieci of the Georgia Institute of Technology. Journal of Computational and Applied Mathematics. 353: 318-344. June 2019. http://doi.org/10.1016/j.cam.2018.12.034

Abstract. We introduce a new technique, which we call the boundary method, for solving semi-discrete optimal transport problems with a wide range of cost functions. The boundary method reduces the effective dimension of the problem, thus improving complexity. For cost functions equal to a p-norm with p ∈ (1,∞), we provide mathematical justification, convergence analysis, and algorithmic development. Our testing supports the boundary method with these p-norms, as well as other, more general cost functions.

• Uniqueness of optimal solutions for semi-discrete transport with p-norm cost functions. May 2017. [arXiv:1705.09383]

Abstract. Semi-discrete transport can be characterized in terms of real-valued shifts. Often, but not always, the solution to the shift-characterized problem partitions the continuous region. This paper gives examples of when partitioning fails, and offers a large class of semi-discrete transport problems where the shift-characterized solution is always a partition.

• Successive Subdivision Methods for transportation networks of images and other grid graphs with Michael Muskulus of the Norwegian University of Science and Technology. Technical Report. February 2016.

Abstract. A variety of methods already exist for computing solutions to discrete optimal transport problems, but all of those methods are designed to work on abstract networks. We propose a new optimal transport technique, the method of successive subdivision, or SSD, as a way of leveraging known positional information to reduce computation time and complexity. We then compare the performance of a specific, multigrid-style SSD against some standard methods, and consider the scaling behavior of our software in order to acquire information about the method鈥檚 average complexity. Our results show that multigrid-style SSD is significantly faster than standard solution methods, especially for large transport problems. We therefore conclude that the SSD approach offers a promising way of using the structure of the embedding space to solve optimal transport problems more efficiently.

• Topological models for 3-configurations with Arthur White of Western Michigan University. October 2014.

Abstract. Models of geometries are desirable for verifying properties of consistency, completeness, and independence of axiom systems. We consider 3-configurations of order v (for 3 ≤ v ≤ 100) and replication number r, with necessarily v ≥ 2r + 1 and 3 | vr. For each of the 1345 such pairs (v, r), we find a topological model for one corresponding 3-configuration, focusing on Steiner Triple Systems and partially balanced incomplete block designs where possible.

Research Presentations

• “A real-valued auction algorithm for optimal transport.” 2018 Conference on Data Analysis poster presentation. March 2018.

Abstract. Optimal transportation theory is an area of mathematics with real-world applications in fields ranging from economics to optimal control to machine learning. We propose a new algorithm for solving discrete transport (network flow) problems, based on classical auction methods. In commerce, auctions are a time-tested method of obtaining optimal object prices from a group of competing bidders. During the 1970s, Dimitri Bertsekas developed an auction-based algorithm, as an alternative to the Hungarian method for the assignment problem. He and David Castañón later published an auction algorithm for integer-valued optimal transport that solves by converting transport problems into assignment problems. The general transport auction method we propose works directly on real-valued transport problems. Our results prove termination, bound the transport error, and relate our algorithm to the algorithm of Bertsekas and Castañón.

• “An auction algorithm for real-valued optimal transport.” Georgia Institute of Technology 10 to 60 celebration talk. December 2017.

Abstract. In commerce, auctions are a time-tested method of obtaining optimal object prices from a group of competing bidders. In the 1970s, Dimitri Bertsekas developed an auction-based algorithm, as an alternative to the Hungarian method for the assignment problem. He and David Casta帽贸n later published an auction algorithm for integer-valued optimal transport that solves by converting transport problems into assignment problems. We propose a more general auction algorithm that works directly on real-valued transport problems and describe its connection to the algorithm of Bertsekas and Castañón.

• “The boundary method for optimal mass transportation and Wasserstein distance computation.” Georgia Institute of Technology Mathematics and Applications Portal Working Group for Problems in Transport and Related Topics in Graphs talk. May 2017.

Abstract. Numerical optimal transport is an important area of research, but many problems are too large and complex for easy computation. Because continuous transport problems are generally solved by conversion to semi-discrete forms, we developed the boundary method for semi-discrete transport. The boundary method works with unaltered ground cost functions. It rapidly identifies region boundaries: locations in the continuous space where transport destinations change. Because the method concentrates computation over those boundaries, rather than the entire continuous space, it reduces the effective dimension of the discretization. The boundary method is an effective mesh generation method, able to solve many transport problems that are intractable using other approaches. Even where other numerical methods exist, our tests indicate that the boundary method's performance will compare favorably.

• “The boundary method for numerical optimal transport.” Georgia Institute of Technology Applied and Computational Mathematics seminar talk. November 2016.

Abstract. The boundary method is a new algorithm for solving semi-discrete transport problems involving a variety of ground cost functions. By reformulating a transport problem as an optimal coupling problem, one can construct a partition of its continuous space whose boundaries allow accurate determination of the transport map and its associated Wasserstein distance. The boundary method approximates region boundaries using the general auction algorithm, controlling problem size with a localized refinement approach. This talk describes numerical and mathematical results obtained when the ground cost is a convex combination of l_p norms, and shares preliminary work involving other ground cost functions.

• “Numerical methods for optimal coupling.” Georgia Institute of Technology College of Sciences School Visits talk. April 2016.

• “Blending continuous and discrete methods to compute optimal transport partitions.” Hale Conference: Dynamics of Evolution Equations poster presentation. March 2016.

Abstract. Optimal transportation can be used to partition a continuous region based on a set of discrete points, but such partitions are difficult to determine exactly and they have been nearly as hard to approximate numerically. We propose a new numerical technique, combining discrete and continuous methods, that generates faster and more accurate results than existing techniques. By considering the optimal transportation problem as an optimal coupling problem, we developed a semi-stable descent method and combined that with a network technique that exploits region continuity to reduce complexity.

• “Computing Optimal Coupling Systems by Blending Continuous and Discrete Methods.” Georgia Scientific Computing Symposium poster presentation and short talk. February 2016.

Research Statement

A brief history of numerical optimal transport, the algorithms I have developed, mathematical contributions, numerical results, and objectives for future research.

National Science Foundation Awards

• Graduate Research Opportunities Worldwide. National Science Foundation. 2015 grant recipient.
• Graduate Research Fellowship Program. National Science Foundation. 2014 recipient.

Other Awards and Activities

• Undergraduate Research and Creative Activities Award. Western Michigan University. 2012 recipient.
• Explorations in Science Research. University of California Berkeley multidisciplinary research experience for undergraduates. 2011 participant.

Explorations in Science Research is a seven day workshop for quantitatively-inclined undergraduates majoring in science, technology, engineering, or mathematics. Students are given the opportunity to work with large data sets of environmentally-relevant information. They are challenged to represent and interpret this data in ways that best communicate its implications to the public. Considering these challenges lets students see how science influences policymaking and general understanding. During the workshop, students gain a basic understanding of computing and visualization tools, and they develop their own data-driven, environmentally-conscious projects.