Approximations for maximum transportation with permutable supply vector and other capacitated star packing problems

Abstract

A study in which non-negative weights were assumed and the total profits were maximized was discussed. It was found that the transportation problem is polynomially solvable even when the flows were required to be integers. One of the problems considered was the variation of the transportation problem known as maximum transportation problem with permutable supply vector. Another related problem was the maximum capacitated star packing which completed a unidirected graph with a non-negative weight function. The special case of TPS with unit demands were called maximum capacitated star-packing in bipartite graphs.