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

DOI10.1002/NET.21507zbMATH Open1338.90068OpenAlexW2005598837MaRDI QIDQ2811304FDOQ2811304

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)

Cites Work

• Title not available (Why is that?)
• A Faster Strongly Polynomial Minimum Cost Flow Algorithm
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• A data structure for dynamic trees
• Perspectives of Monge properties in optimization
• Two special cases of the assignment problem
• Monge properties, discrete convexity and applications
• Dynamic trees in practice
• Fast Matching Algorithms for Points on a Polygon
• Efficient Minimum Cost Matching and Transportation Using the Quadrangle Inequality
• Instant transportation solutions
• The Factored Transportation Problem
• Fast Algorithms for Specially Structured Minimum Cost Flow Problems with Applications
• Simple linear flow decomposition algorithms on trees, circles, and augmented trees

Cited In (5)

• A strongly polynomial algorithm for the transportation problem
• A fast algorithm for constructing Monge sequences in transportation problems with forbidden arcs
• Efficient Algorithms for the Hitchcock Transportation Problem
• Title not available (Why is that?)
• Four-point conditions for the TSP: the complete complexity classification

   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 👍 👎

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)