Patent ID: 8468043
Filing Date: 2013-06-18
Classification: H04W

Abstract:
1. An approximation method carried out by computer-usable program code operable by a computer system for designing a minimum cost network with k-fold redundant coverage of objects to be served by the network, by starting from a collection of potential network elements each having a defined cost value and each having a defined object coverage parameter, and by transforming the collection of potential network elements into a set of network elements that provide the required k-fold redundant coverage at approximate minimum cost, comprising: providing a k-set coverage formulation with the cost values and the object coverage parameter values of the collection of potential network elements; providing a Lagrangian relaxation formulation of the k-set coverage formulation; applying an iterative subgradient optimization algorithm to the Lagrangian relaxation; determining an initial solution found by an iteration of the subgradient optimization algorithm; applying a greedy construction algorithm to add selected elements to the initial solution to form a feasible solution by using the feasible solution to select parameters for the next iteration of the subgradient optimization algorithm, continuing to perform iterations until a set of network elements having an approximate minimum cost solution is identified, and selecting for the network design network elements which are identified in the approximate minimum cost solution from the collection of potential network elements so that the resulting network design will have the required redundancy and approximate minimum cost.