Strongly polynomial algorithms for the quadratic transportation problem with a fixed number of sources

The Transportation problem with a linear objective function is known to be solvable in strongly polynomial time, whereas instances with a convex nonquadratic objective function are not even for cases with the integrality constraints relaxed. The authors present a linear time algorithm for the Continuous Quadratic Transportation problem with two source nodes. Further, they show how problem instances with a fixed number of source (or destination) nodes, k, could be solved in strongly polynomial time, O(n^k’+¹), using an algebraic tree computation model. The algorithms exploit a relatinship between the Transportation problem and the Resource Allocation problem. The strong polynomiality of the algorithms presented here imply the existence of strongly popolynomial algorithms for Integer Quadratic Transportation problems with a fixed number of source nodes as well.