| ERROR ESTIMATION OF THE APPROXIMATION ALGORITHM FOR THE WINDY POSTMAN PROBLEM |
| |
| 作者姓名： | DU Lingu Shandong Textile Engineering College Qingdao China |
| |
| 作者单位： | DU Lingu Shandong Textile Engineering College，Qingdao 266071，China |
| |
| 摘 要： | If we restrict the postman to traversing each edge at most twice in the windypostman problem (WPP), we will get a new problem: 2WPP. An approximation algorithmhas been posed by M. Guan for the WPP. In the present paper, we improve the estimatederror given by M. Guan and show that we can estimate the error for the 2WPP by findinga minimum cost circulation. We also pose a new sufficient condition for the equivalencebetween WPP and 2WPP, which can be checked in polynomial time steps.
|
ERROR ESTIMATION OF THE APPROXIMATION ALGORITHM FOR THE WINDY POSTMAN PROBLEM |
| |
| DU Lingu Shandong Textile Engineering College,Qingdao ,China.ERROR ESTIMATION OF THE APPROXIMATION ALGORITHM FOR THE WINDY POSTMAN PROBLEM[J].Journal of Systems Science and Complexity,1993(2). |
| |
| Authors: | DU Lingu Shandong Textile Engineering College Qingdao China |
| |
| Institution: | DU Lingu Shandong Textile Engineering College,Qingdao 266071,China |
| |
| Abstract: | If we restrict the postman to traversing each edge at most twice in the windy
postman problem (WPP), we will get a new problem: 2WPP. An approximation algorithm
has been posed by M. Guan for the WPP. In the present paper, we improve the estimated
error given by M. Guan and show that we can estimate the error for the 2WPP by finding
a minimum cost circulation. We also pose a new sufficient condition for the equivalence
between WPP and 2WPP, which can be checked in polynomial time steps. |
| |
| Keywords: | Windy postman problem approximation algorithm 2WPP error estimation minimum cost circulation |
| 本文献已被 CNKI 等数据库收录！ |
