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: | Yoshiyuki KARUNO, Tomoaki TACHIBANA, Kougaku YAMASHITA |
---|---|
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 |
Similar Items
-
Permutation groups and combinatotial structures /
by: 306897 Biggs, Norman L., et al.
Published: (1979) -
On the computational complexity of combinatorial problems /
by: 457410 Karp, R. M. -
The Exact Query Complexity of Yes-No Permutation Mastermind
by: Mourad El Ouali, et al.
Published: (2020-04-01) -
An Estimation of Distribution Algorithm for Permutation Flow-Shop Scheduling Problem
by: Sami Lemtenneche, et al.
Published: (2023-07-01) -
Generating functions and enumeration of sequences.
by: Gessel, Ira Martin
Published: (2005)