S-Space College of Engineering/Engineering Practice School (공과대학/대학원) Dept. of Industrial Engineering (산업공학과) Journal Papers (저널논문_산업공학과)
추가제약 최단경로문제를 위한 간단한 완전 다항시간 근사해법군
A Simple Fully Polynomial Approximation Scheme for the Restricted Shortest Path Problem
- 홍성필; 정성진; 박범환
- Issue Date
- Journal of the Korean Institute of Industrial Engineers, 27(4), 379-383
- The restricted shortest path problem is known to be weakly NP-hard and solvable in pseudo-polynomial time. Four fully polynomial approximation schemes (FPAS) are available in the literature, and most of these are based on pseudo-polynomial algorithms. In this paper, we propose a new FPAS that can be easily derived from a combination of a set of standard techniques. Although the complexity of the suggested algorithm is not as good as the fastest one available in the literature, it is practical in the sense that it does not rely on the bound tightening phase based on approximate binary search as in Hassin's fastest algorithm. In addition, we provide a review of standard techniques of existing works as a useful reference.