Preconditioning for the geometric transportation problem

In the geometric transportation problem, we are given a collection of points P in d-dimensional Euclidean space, and each point is given a (positive or negative integer) supply. The goal is to find a transportation map that satisfies the supplies, while minimizing the total distance traveled. This problem has been widely studied in many fields of computer science: from computational geometry, to computer vision, graphics, and machine learning. In this work we study approximation algorithms for the geometric transportation problem. We give an algorithm which, for any fixed dimension d, finds a (1+ε)-approximate transportation map in time nearly-linear in n, and polynomial in ε⁻¹ and in the logarithm of the total positive supply. This is the first approximation scheme for the problem whose running time depends on n as n · polylog(n). Our techniques combine the generalized preconditioning framework of Sherman, which is grounded in continuous optimization, with simple geometric arguments to first reduce the problem to a minimum cost flow problem on a sparse graph, and then to design a good preconditioner for this latter problem.