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: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7234/
Go to the corresponding LIPIcs Volume Portal

Agarwal, Pankaj K. ; Fox, Kyle ; Panigrahi, Debmalya ; Varadarajan, Kasturi R. ; Xiao, Allen

Faster Algorithms for the Geometric Transportation Problem

pdf-format:
LIPIcs-SoCG-2017-7.pdf (0.7 MB)

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},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7234},
  URN =		{urn:nbn:de:0030-drops-72344},
  doi =		{10.4230/LIPIcs.SoCG.2017.7},
  annote =	{Keywords: transportation map, earth mover's distance, shape matching, approximation algorithms}
}

Keywords: transportation map, earth mover's distance, shape matching, approximation algorithms
Collection: 33rd International Symposium on Computational Geometry (SoCG 2017)
Issue Date: 2017
Date of publication: 20.06.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI