B34 Hardness of Approximating Transshipment Problems with Permutable Transit Vectors(Advanced machining technology)
スポンサーリンク
概要
- 論文の詳細を見る
In this paper, we deal with the inapproximability of a transshipment problem with a permutable transit vector. We have already known that the transshipment problem is NP-hard in the strong sense. We prove in this paper that even if the 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. The inapproximability result is obtained by a gap-introducing reduction from an NP-complete problem 3DM.
- 一般社団法人日本機械学会の論文
- 2009-12-01
著者
-
KARUNO Yoshiyuki
Department of Mechanical and System Engineering, Kyoto Institute of Technology
-
Yamashita Kougaku
Kyoto Institute of Technology
-
Karuno Yoshiyuki
Kyoto Institute of Technology
-
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
-
Karuno Yoshiyuki
Department Of Mechanical And System Engineering Faculty Of Engineering And Design Kyoto Institute Of
-
YAMASHITA Kougaku
Department of Mechanical and System Engineering Kyoto Institute of Technology
-
LU Mingzhe
Department of Logistics Management, Dongbei University of Finance & Economics
関連論文
- Optimization Problems and Algorithms in Double-layered Food Packing Systems
- 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)
- 4C1 SCHEDULING MULTIPROCESSOR TASKS WITH PROMPT SERVICE CONSTRAINTS ON ALIGNED IDENTICAL PROCESSORS
- 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
- 1B2 AN APPLICATION OF THE GENETIC ALGORITHM TO A TWO-MACHINE ROBOTIC FLOW-SHOP SCHEDULING PROBLEM(Technical session 1B : Meta Heuristics)
- A SHIFTING BOTTLENECK APPROACH FOR A PARALLEL-MACHINE FLOWSHOP SCHEDULING PROBLEM
- VEHICLE SCHEDULING ON A TREE TO MINIMIZE MAXIMUM LATENESS
- OPTIMAL SCHEDULING FOR AN AUTOMATED m-MACHINE FLOWSHOP
- A Dynamic Programming Based Improvement Heuristic for a Repetitive Routing Problem of Grasp-and-Delivery Robots
- CONSTANT FACTOR APPROXIMATION ALGORITHMS FOR REPETITIVE ROUTING PROBLEMS OF GRASP-AND-DELIVERY ROBOTS IN PRODUCTION OF PRINTED CIRCUIT BOARDS
- Dynamic Programming Algorithms with Data Rounding for Combinatorial Food Packing Problems
- Better Approximation Algorithms for Grasp-and-Delivery Robot Routing Problems
- CONSTANT FACTOR APPROXIMATION ALGORITHMS FOR REPETITIVE ROUTING PROBLEMS OF GRASP-AND-DELIVERY ROBOTS IN PRODUCTION OF PRINTED CIRCUIT BOARDS
- 4A2 NETWORK TRANSFORMATION HEURISTICS FOR MULTI-STORY STORAGE RACK PROBLEMS(Technical session 4A: Material handling system)
- 5B1 IMPROVED IMPLEMENTATION OF AN APPROXIMATION ALGORITHM WITH FACTOR TWO FOR A CYCLIC ROUTING PROBLEM OF GRASP-AND-DELIVERY ROBOTS(Technical session 5B: Routing problems)
- 5B3 APPROXIMATING CYCLIC ROUTING PROBLEMS OF GRASP-AND-DELIVERY ROBOTS IN PRODUCTION OF PRINTED CIRCUIT BOARDS(Technical session 5B: Routing problems)
- Scheduling Capacitated One-Way Vehicles on Paths with Deadlines