 License: Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2017.7
URN: urn:nbn:de:0030-drops-72344
URL: https://drops.dagstuhl.de/opus/volltexte/2017/7234/
 Go to the corresponding LIPIcs Volume Portal

### Faster Algorithms for the Geometric Transportation Problem

 pdf-format:

### Abstract

Let R, B be a set of n points in R^d, for constant d, where the points of R have integer supplies, points of B have integer demands, and the sum of supply is equal to the sum of demand. Let d(.,.) be a suitable distance function such as the L_p distance. The transportation problem asks to find a map tau : R x B --> N such that sum_{b in B}tau(r,b) = supply(r), sum_{r in R}tau(r,b) = demand(b), and sum_{r in R, b in B} tau(r,b) d(r,b) is minimized. We present three new results for the transportation problem when d(.,.) is any L_p metric: * For any constant epsilon > 0, an O(n^{1+epsilon}) expected time randomized algorithm that returns a transportation map with expected cost O(log^2(1/epsilon)) times the optimal cost. * For any epsilon > 0, a (1+epsilon)-approximation in O(n^{3/2}epsilon^{-d}polylog(U)polylog(n)) time, where U is the maximum supply or demand of any point. * An exact strongly polynomial O(n^2 polylog n) time algorithm, for d = 2.

### BibTeX - Entry

```@InProceedings{agarwal_et_al:LIPIcs:2017:7234,
author =	{Pankaj K. Agarwal and Kyle Fox and Debmalya Panigrahi and Kasturi R. Varadarajan and Allen Xiao},
title =	{{Faster Algorithms for the Geometric Transportation Problem}},
booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
pages =	{7:1--7:16},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-038-5},
ISSN =	{1868-8969},
year =	{2017},
volume =	{77},
editor =	{Boris Aronov and Matthew J. Katz},
publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
DROPS-Home | Fulltext Search | Imprint | Privacy 