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

Полное описание

Библиографические подробности

Главные авторы:	Yoshiyuki KARUNO, Tomoaki TACHIBANA, Kougaku YAMASHITA
Формат:	Artigo
Язык:	Inglês
Опубликовано:	The Japan Society of Mechanical Engineers 2010-06-01
Серии:	Journal of Advanced Mechanical Design, Systems, and Manufacturing
Предметы:	combinatorial optimization network flow problems transportation problems permutable transit vectors computational complexity
Online-ссылка:	https://www.jstage.jst.go.jp/article/jamdsm/4/3/4_3_664/_pdf/-char/en
Метки:	Добавить метку Нет меток, Требуется 1-ая метка записи!