Conference proceeding
Faster Algorithms for the Geometric Transportation Problem
Leibniz International Proceedings in Informatics, LIPIcs, Vol.77, pp.71-716
03/19/2019
DOI: 10.4230/lipics.socg.2017.7
Abstract
Let $R$ and $B$ be two point sets in $\mathbb{R}^d$, with $|R|+ |B| = n$ and where $d$ is a constant. Next, let $\lambda : R \cup B \to \mathbb{N}$ such that $\sum_{r \in R } \lambda(r) = \sum_{b \in B} \lambda(b)$ be demand functions over $R$ and $B$. Let $\|\cdot\|$ be a suitable distance function such as the $L_p$ distance. The transportation problem asks to find a map $\tau : R \times B \to \mathbb{N}$ such that $\sum_{b \in B}\tau(r,b) = \lambda(r)$, $\sum_{r \in R}\tau(r,b) = \lambda(b)$, and $\sum_{r \in R, b \in B} \tau(r,b) \|r-b\|$ is minimized. We present three new results for the transportation problem when $\|r-b\|$ is any $L_p$ metric: - For any constant $\varepsilon > 0$, an $O(n^{1+\varepsilon})$ expected time randomized algorithm that returns a transportation map with expected cost $O(\log^2(1/\varepsilon))$ times the optimal cost. - For any $\varepsilon > 0$, a $(1+\varepsilon)$-approximation in $O(n^{3/2}\varepsilon^{-d} \operatorname{polylog}(U) \operatorname{polylog}(n))$ time, where $U = \max_{p\in R\cup B} \lambda(p)$. - An exact strongly polynomial $O(n^2 \operatorname{polylog}n)$ time algorithm, for $d = 2$.
Details
- Title: Subtitle
- Faster Algorithms for the Geometric Transportation Problem
- Creators
- Pankaj K Agarwal - Duke UniversityKyle Fox - Duke UniversityDebmalya Panigrahi - Duke UniversityKasturi R Varadarajan - University of IowaAllen Xiao - Duke University
- Resource Type
- Conference proceeding
- Publication Details
- Leibniz International Proceedings in Informatics, LIPIcs, Vol.77, pp.71-716
- Publisher
- Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, Wadern/Saarbruecken, Germany
- DOI
- 10.4230/lipics.socg.2017.7
- ISSN
- 1868-8969
- Grant note
- 1318996 / National Science Foundation (nsf_________::NSF)
- Language
- English
- Date published
- 03/19/2019
- Academic Unit
- Computer Science
- Record Identifier
- 9984259422102771
Metrics
10 Record Views