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

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

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)

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

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)