Strongly Polynomial Algorithms for the Quadratic Transportation Problem with a Fixed Number of Sources

Abstract

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. We present a linear time algorithm for the Continuous Quadratic Transportation problem (QTP) with two source nodes. Further, we show how problem instances with a fixed number of source (or destination) nodes, k, could be solved in strongly polynomial time, O(n k +1 ), using an algebraic tree computation model. The algorithms exploit a relationship between the Transportation problem and the Resource Allocation problem. The strong polynomiality of the algorithms presented here imply the existence of strongly polynomial algorithms for Integer Quadratic Transportation problems with a fixed number of source nodes as well.