2026-07-27T05:06:45Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7234 2024-03-06T10:39:56Z ddc:004 open_access

Faster Algorithms for the Geometric Transportation Problem Agarwal, Pankaj K. Fox, Kyle Panigrahi, Debmalya Varadarajan, Kasturi R. Xiao, Allen transportation map earth mover's distance shape matching approximation algorithms 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Pankaj K. Agarwal and Kyle Fox and Debmalya Panigrahi and Kasturi R. Varadarajan and Allen Xiao 2017 Is Part Of LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2017.7 urn:nbn:de:0030-drops-72344 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.7 eng https://creativecommons.org/licenses/by/3.0/legalcode