### 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.

Original language | English |
---|---|

Pages (from-to) | 9-16 |

Number of pages | 8 |

Journal | Mathematical Methods of Operations Research |

Volume | 50 |

Issue number | 1 |

DOIs | |

Publication status | Published - 1999 |

## Fingerprint Dive into the research topics of 'A note on the complexity of the transportation problem with a permutable demand vector'. Together they form a unique fingerprint.

## Cite this

Hujter, M., Klinz, B., & Woeginger, G. J. (1999). A note on the complexity of the transportation problem with a permutable demand vector.

*Mathematical Methods of Operations Research*,*50*(1), 9-16. https://doi.org/10.1007/s001860050031