A note on the complexity of the transportation problem with a permutable demand vector |
| |
Authors: | Mihály Hujter Bettina Klinz Gerhard J. Woeginger |
| |
Affiliation: | (1) Department of Mathematics VII, University of Ulm, D-89069 Ulm, Germany |
| |
Abstract: | 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=(b1,
,bn) in order to minimize the overall transportation costs. Meusel and Burkard [6] recently proved that the TP-PD is strongly NP-hard. In their NP-hardness reduction, the used demand values bj, j=1,
,n, are large integers. In this note we show that the TP-PD remains strongly NP-hard even for the case where bj]{0,3} for j=1,
,n. As a positive result, we show that the TP-PD becomes strongly polynomial time solvable if bj] {0,1,2} holds for j=1,
,n. This result can be extended to the case where bj]{3,3+1,3+2} for an integer 3. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|