Faster algorithms for the geometric transportation problem

DOI10.4230/LIPICS.SOCG.2017.7MaRDI QIDQ4580079zbMATH OpenFDO

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

Publication date 13 August 2018

Full work available at URL https://arxiv.org/abs/1903.08263

zbMATH Keywords

approximation algorithmsearth mover's distanceshape matchingtransportation map

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Randomized algorithms (68W20) Approximation algorithms (68W25) Analysis of algorithms (68W40)

Recommendations

• Algorithms for the transportation problem in geometric settings
• Using geometry to solve the transportation problem in the plane
• scientific article; zbMATH DE number 742962
• Preconditioning for the Geometric Transportation Problem
• Preconditioning for the geometric transportation problem

Cited in

(20)

• Using geometry to solve the transportation problem in the plane
• Rényi 100, quantitative and qualitative (in)dependence
• Fast Algorithms for Geometric Traveling Salesman Problems
• Fast Heuristics for Large Geometric Traveling Salesman Problems
• scientific article; zbMATH DE number 1156568 (Why is no real title available?)
• Impossibility of sketching of the 3D transportation metric with quadratic cost
• Preconditioning for the geometric transportation problem
• On geometric prototype and applications
• Efficient algorithms for geometric partial matching
• Preconditioning for the Geometric Transportation Problem
• A weighted approach to the maximum cardinality bipartite matching problem with applications in geometric settings
• Parallel algorithms for geometric graph problems
• Geometric median in nearly linear time
• Algorithms for the transportation problem in geometric settings
• Light Euclidean Spanners with Steiner Points
• scientific article; zbMATH DE number 7650079 (Why is no real title available?)
• A near-linear time approximation scheme for geometric transportation with arbitrary supplies and spread
• A near-linear time approximation scheme for geometric transportation with arbitrary supplies and spread
• A data-dependent approach for high-dimensional (robust) Wasserstein alignment
• A fast algorithm for constructing Monge sequences in transportation problems with forbidden arcs

This page was built for publication: Faster algorithms for the geometric transportation problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4580079)