A decomposition algorithm for linear relaxation of the weigted r-covering problem

From MaRDI portal





The linear relaxation of the weighted r-covering problem (r-LCP) is considered. The dual problem (c-LMP) is the linear relaxation of the well-known c-matching problem and hence can be solved in polynomial time. However, we describe a simple, but nonpolynomial algorithm in which the r-LCP is decomposed into a sequence of 1-LCP's and its optimal solution is obtained by adding the optimal solutions of these 1-LCP's. An 1-LCP can be solved in polynomial time by solving its dual as a max-flow problem on a bipartite graph. An accelerated algorithm based on this decomposition scheme to solve an r-LCP is also developed and its average case behaviour is studied.











This page was built for publication: A decomposition algorithm for linear relaxation of the weigted r-covering problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3688125)