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$.
Categories: cs.DS