Back to search

Georgia Institute of Technology

The boundary method and general auction for optimal mass transportation and Wasserstein distance computation

Abstract

dc:description.abstract

Numerical optimal transport is an important area of research, but most problems are too large and complex for easy computation. Because continuous transport problems are generally solved by conversion to either discrete or semi-discrete forms, I focused on methods for those two. I developed a discrete algorithm specifically for fast approximation with controlled error bounds: the general auction method. It works directly on real-valued transport problems, with guaranteed termination and \emph{a priori} error bounds. I also developed the boundary method for semi-discrete transport. It works on unaltered ground cost functions, rapidly identifying locations in the continuous space where transport destinations change. Because the method computes over region boundaries, rather than the entire continuous space, it reduces the effective dimension of the discretization. The general auction is the first relaxation method designed for compatibility with real-valued costs and weights. The boundary method is the first transport technique designed explicitly around the semi-discrete problem and the first to use the shift characterization to reduce dimensionality. No truly comparable methods exist. The general auction and boundary method are able to solve many transport problems that are intractable using other approaches. Even where other solution methods exist, my tests indicate that the general auction and boundary method outperform them.

Degree

thesis:*
Level thesis:degree_level
Doctoral
Department dc:contributor.department
Mathematics
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2017

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Walsh, Joseph Donald
Advisor dc:contributor.advisor
  • Dieci, Luca
Committee members dc:contributor.committeemember
  • Zhou, Hao-Min
  • Kang, Sung Ha
  • Muskulus, Michael
  • Yezzi, Anthony

Subjects

dc:subject × 8

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1853/58701

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Walsh, Joseph Donald. The boundary method and general auction for optimal mass transportation and Wasserstein distance computation. Doctoral thesis, Georgia Institute of Technology, 2017. http://hdl.handle.net/1853/58701