Hujter, Mihály; Klinz, Bettina; Woeginger, Gerhard J. A note on the complexity of the transportation problem with a permutable demand vector. (English) Zbl 0967.90081 Math. Methods Oper. Res. 50, No. 1, 9-16 (1999). Summary: In this note we investigate the computational complexity of the transportation problem with a permutable demand vector, TP-PD for short. In the TP-PD, the goal is to permute the elements of the given integer demand vector \(b=(b_1,\dots,b_n)\) in order to minimize the overall transportation costs. S. G. Meusel and R. E. Burkard [ibid. 50, 1-7 (1999; Zbl 0967.90084)] recently proved that the TP-PD is strongly NP-hard. In their NP-hardness reduction, the used demand values \(b_j\), \(j=1,\dots,n\), are large integers. In this note we show that the TP-PD remains strongly NP-hard even for the case where \(b_j\in\{0,3\}\) for \(j=1,\dots,n\). As a positive result, we show that the TP-PD becomes strongly polynomial time solvable if \(b_j\in \{0, 1,2\}\) holds for \(j=1,\dots,n\). This result can be extended to the case where \(b_j\in \{\kappa, \kappa+1, \kappa+2\}\) for an integer \(\kappa\). Cited in 1 Document MSC: 90C08 Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) 90C60 Abstract computational complexity for mathematical programming problems Keywords:transportation problem; permutable demand vector; computational complexity; minimum weight \(f\)-factor problem Citations:Zbl 0967.90084 PDFBibTeX XMLCite \textit{M. Hujter} et al., Math. Methods Oper. Res. 50, No. 1, 9--16 (1999; Zbl 0967.90081)