AN INAPPROXIMABILITY OF TRANSSHIPMENT PROBLEMS WITH PERMUTABLE TRANSIT VECTORS
スポンサーリンク
概要
- 論文の詳細を見る
We investigate the hardness of approximating a transshipment problem with a permutable transit vector. We have already known that the transshipment problem of minimizing the total shipping cost is NP-hard. In this paper, we prove that even if the unit shipping cost associated with every arc is given as a positive integer, there is no polynomial time constant factor approximation algorithm for the transshipment problem under the hypothesis that P≠NP. We obtain the inapproximability result by a gap-introducing reduction from an NP-complete problem by the name of 3DM. On the other hand, we propose a preparatory heuristic algorithm to the transshipment problem, which is based on a relaxation into the minimum cost flow problem and the minimum weight perfect matching on a bipartite graph. We also provide an upper bound of the total shipping cost obtained by the proposed heuristic.
著者
-
Yamashita Kougaku
Kyoto Institute of Technology
-
Karuno Yoshiyuki
Kyoto Institute of Technology
-
Lu Mingzhe
Dongbei University of Finance & Economics
-
Yamashita Kougaku
Dep. Of Mechanical And System Engineering Kyoto Inst. Of Technol.
-
Karuno Yoshiyuki
Dep. Of Mechanical And System Engineering Kyoto Inst. Of Technol.
-
Lu Mingzhe
Dongbei Finance University
-
Lu Mingzhe
Dongbei University Of Finance & Economics
関連論文
- AN INAPPROXIMABILITY OF TRANSSHIPMENT PROBLEMS WITH PERMUTABLE TRANSIT VECTORS
- 1A1 COMBINATORIAL OPTIMIZATION PROBLEMS AND ALGORITHMS IN DOUBLE-LAYERED FOOD PACKING EQUIPMENTS
- 3B4 ON OPTIMAL SCHEDULING PROBLEMS FOR PARALLLEL MACHINES WITH A SINGLE SERVER(Technical session 3B : Combinatorics 2)
- BI-CRITERIA FOOD PACKING BY DYNAMIC PROGRAMMING(the 50th Anniversary of the Operations Research Society of Japan)
- B34 Hardness of Approximating Transshipment Problems with Permutable Transit Vectors(Advanced machining technology)
- 3C3 A TRANSSHIPMENT PROBLEM WITH A PREMUTABLE TRANSIT VECTOR
- ANALYSIS AND OPTIMIZATION FOR AUTOMATED VEHICLE ROUTING ON A SINGLE LOOP(Advanced Planning and Scheduling for Supply Chain Management)
- 2-B-5 A HEURISTIC ALGORITHM FOR OPERATING A PERMUTATIONAL CIRCULATION-TYPE VEHICLE ROUTING SYSTEM
- A SHIFTING BOTTLENECK APPROACH FOR A PARALLEL-MACHINE FLOWSHOP SCHEDULING PROBLEM
- OPTIMAL SCHEDULING FOR AN AUTOMATED m-MACHINE FLOWSHOP
- CONSTANT FACTOR APPROXIMATION ALGORITHMS FOR REPETITIVE ROUTING PROBLEMS OF GRASP-AND-DELIVERY ROBOTS IN PRODUCTION OF PRINTED CIRCUIT BOARDS