Complexity of the Transshipment Problem with a Permutable Transit Vector
In this paper, we show that the transshipment problem with a permutable transit vector remains NP-hard even when each entry of the given transit vector takes either zero or two. We prove the hardness by a reduction from an NP-complete problem by the name of 3DM. We also show that the transshipment p...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
The Japan Society of Mechanical Engineers
2010-06-01
|
| Series: | Journal of Advanced Mechanical Design, Systems, and Manufacturing |
| Subjects: | |
| Online Access: | https://www.jstage.jst.go.jp/article/jamdsm/4/3/4_3_664/_pdf/-char/en |
| Summary: | In this paper, we show that the transshipment problem with a permutable transit vector remains NP-hard even when each entry of the given transit vector takes either zero or two. We prove the hardness by a reduction from an NP-complete problem by the name of 3DM. We also show that the transshipment problem can be solved in polynomial time if each entry of the transit vector takes either zero or one. We obtain the time complexity by applying the successive shortest path algorithm for the minimum cost flow problem. |
|---|---|
| ISSN: | 1881-3054 |