A note on the complexity of the transportation problem with a permutable demand vector

A note on the complexity of the transportation problem with a permutable demand vector

0.00 Avg rating0 Votes
Article ID: iaor20002212
Country: Germany
Volume: 50
Issue: 1
Start Page Number: 9
End Page Number: 16
Publication Date: Jan 1999
Journal: Mathematical Methods of Operations Research (Heidelberg)
Authors: , ,
Keywords: programming: transportation
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 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 ∈ {κ,κ + 1, κ + 2} for an integer κ.

Reviews

Required fields are marked *. Your email address will not be published.