Our interest in this paper is in the efficient computation of a good low bound for the traveling salesman problem and is in the application of a network problem in agriculture. We base our approach on a relatively new formulation of the TSP as a two-commodity network flow problem. By assigning Lagrangian multipliers to certain constraints and relaxing them, the problem separates into two single-commodity network flow problems and an assignment problem, for which efficient algorithms are available.

• 황인극 | Hwang, In-Keuk
• 박동진 | Park, Dong-Jin
• 윤광식 | Yoon, Kwang-Sik