Approximation Algorithms for Some Postman Problems

Abstract

Approxtmatton algorithms for several NP-complete edge-covermg routing problems are presented and analyzed m terms of the worst-case ratio of the cost of the obtained solutmn to the cost of the optimum solutton A worst-case bound of 2 is proved for the mixed postman algortthm of Edmonds and Johnson, and a related algorithm for the mixed postman problem is shown also to have a worst-case bound of 2 A mixed strategy approach ts used to obtain a bound of ~ for the mixed postman problem A second mixed strategy algorithm, for the mtxed postman on a planar graph, ~s shown to have a worst-case bound of KEY WORDS AND PHRASES Chinese postman problem, mixed postman problem, rural postman problem, NPcomplete problems, polynomml-tlme approximation algorithm, heunsuc, worst-case performance bound, m,xed strategy CR CATEGORIES 5 25, 5 39, 8