Faster strongly polynomial algorithms for the unbalanced transportation problem and assignment problem with Monge costs

DOI10.1002/NET.21507MaRDI QIDQ2811304zbMATH OpenOpenAlexFDO

Authors Balachandran Vaidyanathan

Publication date 10 June 2016

Published in Networks (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/net.21507

zbMATH Keywords

computational complexityassignment problemtransportation problemMonge matrixminimum cost flow problemnetworks flow algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Transportation, logistics and supply chain management (90B06)

Recommendations

• A faster polynomial algorithm for the unbalanced Hitchcock transportation problem
• A strongly polynomial algorithm for the transportation problem
• Strongly Polynomial Algorithms for the Quadratic Transportation Problem with a Fixed Number of Sources
• Strongly polynomial algorithm for a production-transportation problem with concave production cost
• Fast transport optimization for Monge costs on the circle
• POLYNOMIAL TIME INTERIOR POINT ALGORITHMS FOR TRANSPORTATION PROBLEMS
• Polynomial-time algorithms for multimarginal optimal transport problems with structure
• A strongly polynomial algorithm for the uniform balanced network flow problem
• A strongly polynomial algorithm for a concave production-transportation problem with a fixed number of nonlinear variables
• A polynomial algorithm for an integer quadratic non-separable transportation problem

Cites work

• A Faster Strongly Polynomial Minimum Cost Flow Algorithm
• A data structure for dynamic trees
• Dynamic trees in practice
• Efficient Minimum Cost Matching and Transportation Using the Quadrangle Inequality
• Fast Matching Algorithms for Points on a Polygon
• Fast algorithms for specially structured minimum cost flow problems with applications
• Instant transportation solutions
• Monge properties, discrete convexity and applications
• Network flows. Theory, algorithms, and applications.
• Perspectives of Monge properties in optimization
• Simple linear flow decomposition algorithms on trees, circles, and augmented trees
• The Factored Transportation Problem
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• Two special cases of the assignment problem

Cited in

(6)

• A linear time algorithm for the unbalanced Hitchcock transportation problem
• A fast algorithm for constructing Monge sequences in transportation problems with forbidden arcs
• Four-point conditions for the TSP: the complete complexity classification
• Efficient Algorithms for the Hitchcock Transportation Problem
• scientific article; zbMATH DE number 2154257 (Why is no real title available?)
• A strongly polynomial algorithm for the transportation problem

This page was built for publication: Faster strongly polynomial algorithms for the unbalanced transportation problem and assignment problem with Monge costs

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