Document Open Access Logo

A Near-Linear Time Approximation Scheme for Geometric Transportation with Arbitrary Supplies and Spread

Authors Kyle Fox, Jiashuai Lu

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2020.45.pdf
  • Filesize: 0.6 MB
  • 18 pages

Document Identifiers

Author Details

Kyle Fox
  • Department of Computer Science, The University of Texas at Dallas, TX, USA
Jiashuai Lu
  • Department of Computer Science, The University of Texas at Dallas, TX, USA

Acknowledgements

The authors would like to thank Hsien-Chih Chang for some helpful discussions that took place with the first author at Dagstuhl seminar 19181 "Computational Geometry". We would also like to thank the anonymous reviewers for many helpful comments and suggestions.

Cite AsGet BibTex

Kyle Fox and Jiashuai Lu. A Near-Linear Time Approximation Scheme for Geometric Transportation with Arbitrary Supplies and Spread. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 45:1-45:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.SoCG.2020.45

Abstract

The geometric transportation problem takes as input a set of points P in d-dimensional Euclidean space and a supply function μ : P → ℝ. The goal is to find a transportation map, a non-negative assignment τ : P × P → ℝ_{≥ 0} to pairs of points, so the total assignment leaving each point is equal to its supply, i.e., ∑_{r ∈ P} τ(q, r) - ∑_{p ∈ P} τ(p, q) = μ(q) for all points q ∈ P. The goal is to minimize the weighted sum of Euclidean distances for the pairs, ∑_{(p, q) ∈ P × P} τ(p, q) ⋅ ||q - p||₂. We describe the first algorithm for this problem that returns, with high probability, a (1 + ε)-approximation to the optimal transportation map in O(n poly(1 / ε) polylog n) time. In contrast to the previous best algorithms for this problem, our near-linear running time bound is independent of the spread of P and the magnitude of its real-valued supplies.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
  • Theory of computation → Network flows
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

Related Versions

References

  1. Pankaj K. Agarwal, Kyle Fox, Debmalya Panigrahi, Kasturi R. Varadarajan, and Allen Xiao. Faster algorithms for the geometric transportation problem. In Proc. 33rd Intern. Symp. Comput. Geom., pages 7:1-7:16, 2017. URL: https://doi.org/10.4230/LIPIcs.SoCG.2017.7.
  2. Pankaj K. Agarwal and R. Sharathkumar. Approximation algorithms for bipartite matching with metric and geometric costs. In Proc. 46th Symp. Theory Comput., pages 555-564. ACM, 2014. URL: https://doi.org/10.1145/2591796.2591844.
  3. Alexandr Andoni, Aleksandar Nikolov, Krzysztof Onak, and Grigory Yaroslavtsev. Parallel algorithms for geometric graph problems. In Proc. 46th Symp. Theory Comput., pages 574-583, 2014. URL: https://doi.org/10.1145/2591796.2591805.
  4. Marshall W. Bern, David Eppstein, and Shang-Hua Teng. Parallel construction of quadtrees and quality triangulations. Int. J. Comput. Geometry Appl., 9(6):517-532, 1999. URL: https://doi.org/10.1142/S0218195999000303.
  5. Nicolas Bonneel, Michiel van de Panne, Sylvain Paris, and Wolfgang Heidrich. Displacement interpolation using Lagrangian mass transport. ACM Trans. Graph., 30(6):158, 2011. URL: https://doi.org/10.1145/2070781.2024192.
  6. Paul B. Callahan and S. Rao Kosaraju. Faster algorithms for some geometric graph problems in higher dimensions. In Proc. 4th Ann. ACM/SIGACT-SIAM Symp. Discrete Algorithms, pages 291-300, 1993. URL: http://dl.acm.org/citation.cfm?id=313559.313777.
  7. Marco Cuturi and Arnaud Doucet. Fast computation of Wasserstein barycenters. In Proc. 31st Intern. Conf. Machine Learning, pages 685-693, 2014. URL: http://proceedings.mlr.press/v32/cuturi14.html.
  8. Panos Giannopoulos and Remco C. Veltkamp. A pseudo-metric for weighted point sets. In Proc. 7th Europ. Conf. Comput. Vision, pages 715-730, 2002. URL: https://doi.org/10.1007/3-540-47977-5_47.
  9. Kristen Grauman and Trevor Darrell. Fast contour matching using approximate earth mover’s distance. In Proc. 24th IEEE Conf. Comput. Vision and Pattern Recog., pages I:220-I:227, 2004. URL: https://doi.org/10.1109/CVPR.2004.104.
  10. Sariel Har-Peled. Geometric approximation algorithms, volume 173. American Mathematical Soc., 2011. Google Scholar
  11. Piotr Indyk. A near linear time constant factor approximation for Euclidean bichromatic matching (cost). In Proc. 18th Ann. ACM-SIAM Symp. Discrete Algorithms, pages 39-42, 2007. URL: http://dl.acm.org/citation.cfm?id=1283383.1283388.
  12. Andrey Boris Khesin, Aleksandar Nikolov, and Dmitry Paramonov. Preconditioning for the geometric transportation problem. In Proc. 35th Intern. Symp. Comput. Geom., pages 15:1-15:14, 2019. URL: https://doi.org/10.4230/LIPIcs.SoCG.2019.15.
  13. Nathaniel Lahn, Deepika Mulchandani, and Sharath Raghvendra. A graph theoretic additive approximation of optimal transport. In Proc 32nd Adv. Neur. Info. Proces. Sys., pages 13813-13823, 2019. URL: http://papers.nips.cc/paper/9533-a-graph-theoretic-additive-approximation-of-optimal-transport.
  14. Yin Tat Lee and Aaron Sidford. Path finding methods for linear programming: Solving linear programs in ~o(vrank) iterations and faster algorithms for maximum flow. In Proc. 55th IEEE Ann. Symp. Found. Comput. Sci., pages 424-433, 2014. URL: https://doi.org/10.1109/FOCS.2014.52.
  15. James B. Orlin. A faster strongly polynomial minimum cost flow algorithm. Operations Research, 41(2):338-350, 1993. URL: https://doi.org/10.1287/opre.41.2.338.
  16. Yossi Rubner, Carlo Tomasi, and Leonidas J. Guibas. The earth mover’s distance as a metric for image retrieval. Intern. J. Comput. Vision, 40(2):99-121, 2000. URL: https://doi.org/10.1023/A:1026543900054.
  17. R. Sharathkumar and Pankaj K. Agarwal. Algorithms for the transportation problem in geometric settings. In Proc. 23rd Ann. ACM-SIAM Symp. Discrete Algorithms, pages 306-317, 2012. URL: https://doi.org/10.1137/1.9781611973099.29.
  18. R. Sharathkumar and Pankaj K. Agarwal. A near-linear time ε-approximation algorithm for geometric bipartite matching. In Proc. 44th Symp. Theory Comput., pages 385-394, 2012. URL: https://doi.org/10.1145/2213977.2214014.
  19. Jonah Sherman. Generalized preconditioning and undirected minimum-cost flow. In Proc. 28th Ann. ACM-SIAM Symp. Discrete Algorithms, pages 772-780, 2017. URL: https://doi.org/10.1137/1.9781611974782.49.
  20. Daniel Dominic Sleator and Robert Endre Tarjan. Self-adjusting binary search trees. J. ACM, 32(3):652-686, 1985. URL: https://doi.org/10.1145/3828.3835.
  21. Justin Solomon, Raif M. Rustamov, Leonidas J. Guibas, and Adrian Butscher. Earth mover’s distances on discrete surfaces. ACM Trans. Graph., 33(4):67:1-67:12, 2014. URL: https://doi.org/10.1145/2601097.2601175.
  22. Cédric Villani. Optimal Transport: Old and New. 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 Imprint Privacy Contact