Preconditioning for the Geometric Transportation Problem

DOI10.4230/LIPICS.SOCG.2019.15MaRDI QIDQ5088942zbMATH OpenOpenAlexFDO

Authors Andrey Boris Khesin, Aleksandar Nikolov, Dmitry Paramonov

Publication date 18 July 2022

Full work available at URL https://doi.org/10.4230/LIPIcs.SoCG.2019.15

zbMATH Keywords

Earth mover distanceminimum cost flowtransportation problem

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Transportation, logistics and supply chain management (90B06)

Recommendations

• Preconditioning for the geometric transportation problem
• Preconditioning of optimal transport
• Algorithms for the transportation problem in geometric settings
• Faster algorithms for the geometric transportation problem
• scientific article; zbMATH DE number 4172739
• scientific article; zbMATH DE number 1200264
• Special preconditioners for solution of transport-dominated convection-diffusion problem
• POLYNOMIAL TIME INTERIOR POINT ALGORITHMS FOR TRANSPORTATION PROBLEMS
• Solving generalized transportation problems via pure transportation problems
• scientific article; zbMATH DE number 3974683

Cites work

• A near-linear time ε-approximation algorithm for geometric bipartite matching
• Algorithms for the transportation problem in geometric settings
• Approximation algorithms for bipartite matching with metric and geometric costs
• Faster algorithms for the geometric transportation problem
• Generalized preconditioning and undirected minimum-cost flow
• scientific article; zbMATH DE number 6381629 (Why is no real title available?)
• scientific article; zbMATH DE number 2062646 (Why is no real title available?)
• Optimal transportation and applications. Lectures given at the C. I. M. E. summer school, Martina Franca, Italy, September 2--8, 2001
• Parallel algorithms for geometric graph problems
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Similarity estimation techniques from rounding algorithms
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• The earth mover's distance as a metric for image retrieval

Cited in

(8)

• Using geometry to solve the transportation problem in the plane
• Faster algorithms for the geometric transportation problem
• Preconditioning for the geometric transportation problem
• Algorithms for the transportation problem in geometric settings
• 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

This page was built for publication: Preconditioning for the Geometric Transportation Problem

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