About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Algorithmica (New York)
Paper
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.