# Faster algorithms for the geometric transportation problem

Conference Paper

Let R, B C R for constant d, be two point sets with |R| + |B| = n, and let λ: R∪B → ℕ such that Σ λ(r) = Σ λ (b) be demand functions over R and B. Let d(·, ·) be a suitable distance function such as the L distance. The transportation problem asks to find a map τ: R × B → ℕ such that Σ τ(r, b) = λ(r), Σ τ(r, b) = λ(b), and σ τ(r, b)d(r, b) is minimized. We present three new results for the transportation problem when d(·, ·) is any L metric: • For any constant ϵ > 0, an O(n ) expected time randomized algorithm that returns a transportation map with expected cost O(log (1/ϵ)) times the optimal cost. • For any ϵ > 0, a (1 + ϵ)-approximation in O(n ϵ polylog(U) polylog(n)) time, where U = max λ (p). •An exact strongly polynomial O(n polylogn) time algorithm, for d = 2. d 1+ϵ 2 3/2 -d 2 r∈R b∈B p b∈B r∈R r∈Rb∈B p p∈Rcup;B

### Full Text

### Duke Authors

### Cited Authors

- Agarwal, PK; Fox, K; Panigrahi, D; Varadarajan, KR; Xiao, A

### Published Date

- June 1, 2017

### Published In

### Volume / Issue

- 77 /

### Start / End Page

- 71 - 716

### International Standard Serial Number (ISSN)

- 1868-8969

### International Standard Book Number 13 (ISBN-13)

- 9783959770385

### Digital Object Identifier (DOI)

- 10.4230/LIPIcs.SoCG.2017.7

### Citation Source

- Scopus