Document Open Access Logo

Faster Algorithms for the Geometric Transportation Problem

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

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2017.7.pdf
  • Filesize: 0.69 MB
  • 16 pages

Document Identifiers

Author Details

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

Cite As Get BibTex

Pankaj K. Agarwal, Kyle Fox, Debmalya Panigrahi, Kasturi R. Varadarajan, and Allen Xiao. Faster Algorithms for the Geometric Transportation Problem. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 7:1-7:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.SoCG.2017.7

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.

Subject Classification

Keywords
  • transportation map
  • earth mover's distance
  • shape matching
  • approximation algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Pankaj K. Agarwal, Alon Efrat, and Micha Sharir. Vertical decomposition of shallow levels in 3-dimensional arrangements and its applications. SIAM J. Comput., 29(3):912-953, 1999. URL: http://dx.doi.org/10.1137/S0097539795295936.
  2. Pankaj K. Agarwal and Jeff Erickson. Geometric range searching and its relatives. Contemporary Mathematics, 223:1-56, 1999. Google Scholar
  3. Pankaj K. Agarwal and Kasturi R. Varadarajan. A near-linear constant-factor approximation for Euclidean bipartite matching? In Proc. of the 20superscriptth ACM Symp. on Comp. Geometry, pages 247-252, 2004. URL: http://dx.doi.org/10.1145/997817.997856.
  4. Alexandr Andoni, Aleksandar Nikolov, Krzysztof Onak, and Grigory Yaroslavtsev. Parallel algorithms for geometric graph problems. In Proc. of the 46superscriptth Ann. ACM Symp. on Theory of Comp., pages 574-583, 2014. URL: http://dx.doi.org/10.1145/2591796.2591805.
  5. Sanjeev Arora. Polynomial time approximation schemes for Euclidean TSP and other geometric problems. In Proc. of the 37superscriptth Ann. IEEE Symp. on Found. of Comp. Sci., pages 2-11, 1996. URL: http://dx.doi.org/10.1109/SFCS.1996.548458.
  6. Sunil Arya, Gautam Das, David M. Mount, Jeffrey S. Salowe, and Michiel H. M. Smid. Euclidean spanners: short, thin, and lanky. In Proc. of the 27superscriptth Ann. ACM Symp. on Theory of Comp., pages 489-498, 1995. URL: http://dx.doi.org/10.1145/225058.225191.
  7. Sunil Arya, David M. Mount, and Michiel H. M. Smid. Randomized and deterministic algorithms for geometric spanners of small diameter. In Proc. of the 35superscriptth Ann. IEEE Symp. on Found. of Comp. Sci., pages 703-712, 1994. URL: http://dx.doi.org/10.1109/SFCS.1994.365722.
  8. David S. Atkinson and Pravin M. Vaidya. Using geometry to solve the transportation problem in the plane. Algorithmica, 13(5):442-461, 1995. Google Scholar
  9. Sergio Cabello, Panos Giannopoulos, Christian Knauer, and Günter Rote. Matching point sets with respect to the Earth Mover’s Distance. Comput. Geom., 39(2):118-133, 2008. URL: http://dx.doi.org/10.1016/j.comgeo.2006.10.001.
  10. Paul B. Callahan and S. Rao Kosaraju. Faster algorithms for some geometric graph problems in higher dimensions. In Proc. of the 4superscriptth Ann. ACM/SIGACT-SIAM Symp. on Discrete Algo., pages 291-300, 1993. URL: http://dl.acm.org/citation.cfm?id=313559.313777.
  11. Paul B. Callahan and S. Rao Kosaraju. A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields. J. ACM, 42(1):67-90, 1995. URL: http://dx.doi.org/10.1145/200836.200853.
  12. Marco Cuturi and Arnaud Doucet. Fast computation of Wasserstein barycenters. In Proc. of the 31superscriptth Internat. Conf. on Machine Learning, pages 685-693, 2014. URL: http://jmlr.org/proceedings/papers/v32/cuturi14.html.
  13. Alexandre Gramfort, Gabriel Peyré, and Marco Cuturi. Fast optimal transport averaging of neuroimaging data. In Proc. of the 24superscriptth Internat. Conf. on Infor. Processing in Medical Imaging, pages 261-272. Springer, 2015. Google Scholar
  14. Kristen Grauman and Trevor Darrell. Fast contour matching using approximate earth mover’s distance. In Proc. of the 24superscriptth Ann. IEEE Conf. on Comp. Vision and Pattern Recog., volume 1, pages I-220. IEEE, 2004. Google Scholar
  15. Sariel Har-Peled. Geometric Approximation Algorithms, volume 173. American Mathematical Society Providence, 2011. Google Scholar
  16. Piotr Indyk. A near linear time constant factor approximation for Euclidean bichromatic matching (cost). In Proc. of the 18superscriptth Ann. ACM-SIAM Symp. on Discrete Algo., pages 39-42, 2007. URL: http://dl.acm.org/citation.cfm?id=1283383.1283388.
  17. Haim Kaplan, Wolfgang Mulzer, Liam Roditty, Paul Seiferth, and Micha Sharir. Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications. CoRR, abs/1604.03654, 2016. URL: http://arxiv.org/abs/1604.03654.
  18. Yin Tat Lee and Aaron Sidford. Path finding methods for linear programming: Solving linear programs in Õ(vrank) iterations and faster algorithms for maximum flow. In Proc. of the 55superscriptth Ann. IEEE Symp. on Found. of Comp. Sci., pages 424-433, 2014. Google Scholar
  19. James B. Orlin. A faster strongly polynominal minimum cost flow algorithm. In Proc. of the 20superscriptth Annual ACM Symp. on Theory of Comp., May 2-4, 1988, Chicago, Illinois, USA, pages 377-387, 1988. URL: http://dx.doi.org/10.1145/62212.62249.
  20. Yossi Rubner, Carlo Tomasi, and Leonidas J. Guibas. A metric for distributions with applications to image databases. In 6superscriptth Internat. Conf. on Comp. Vision, pages 59-66, 1998. URL: http://dx.doi.org/10.1109/ICCV.1998.710701.
  21. R. Sharathkumar and Pankaj K. Agarwal. Algorithms for the transportation problem in geometric settings. In Proc. of the 23superscriptrd Ann. ACM-SIAM Symp. on Discrete Algo., pages 306-317, 2012. URL: http://portal.acm.org/citation.cfm?id=2095145&CFID=63838676&CFTOKEN=79617016.
  22. R. Sharathkumar and Pankaj K. Agarwal. A near-linear time ε-approximation algorithm for geometric bipartite matching. In Proc. of the 44superscriptth Ann. ACM Symp. on Theory of Comp., pages 385-394, 2012. URL: http://dx.doi.org/10.1145/2213977.2214014.
  23. Justin Solomon, Raif M. Rustamov, Leonidas J. Guibas, and Adrian Butscher. Earth mover’s distances on discrete surfaces. ACM Transactions on Graphics, 33(4):67:1-67:12, 2014. URL: http://dx.doi.org/10.1145/2601097.2601175.
  24. Kunal Talwar. Bypassing the embedding: Algorithms for low dimensional metrics. In Proc. of the 36superscriptth Ann. ACM Symp. on Theory of Comp., pages 281-290, 2004. URL: http://dx.doi.org/10.1145/1007352.1007399.
  25. Pravin M. Vaidya. Geometry helps in matching. SIAM J. Comput., 18(6):1201-1225, 1989. Google Scholar
  26. Kasturi R. Varadarajan and Pankaj K. Agarwal. Approximation algorithms for bipartite and non-bipartite matching in the plane. In Proc. of the 10superscriptth Ann. ACM-SIAM Symp. on Discrete Algo., pages 805-814, 1999. URL: http://dl.acm.org/citation.cfm?id=314500.314918.
  27. Cédric Villani. Optimal Transport: Old and New, volume 338. Springer Science &Business Media, 2008. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact