Patent ID: 8660037
Filing Date: 2014-02-25
Classification: H04L

Abstract:
1. An approximation method for designing a minimum total cost network by selecting from a collection of available network elements which include nodes and links connecting the nodes, comprising: selecting graph edges to correspond to the available links; assigning edge costs that correspond to the link costs; selecting graph vertices to correspond to nodes; selecting pairs of vertices that are required to be in the network; assigning penalty costs to those required pairs of vertices that are not connected; constructing a relaxation of a linear programming problem incorporating values for edge costs, pair requirements and penalty costs and having coefficients for edge costs and penalty costs as variables; in a computer processor, finding an optimal basic feasible solution to the relaxation of the linear programming problem; in a computer processor, applying a selection criterion to pairs and edges in the optimal basic solution; in a computer processor, paying a penalty cost for each pair selected according to the selection criterion and including the penalty cost in the network solution; in a computer processor, including each edge selected according to the selection criterion in the network solution; in a computer processor, forming a residual graph including all remaining required pairs with unpaid penalties and including all edges; in a computer processor, constructing a residual linear programming problem for the residual graph in which edge coefficients for edges selected according to the selection criterion are set to 1 and other edge coefficients are variables; in a computer processor, iteratively repeating the previous elements from the finding element to the constructing element, using the residual linear programming problem from an immediately previous iteration, until all the required pairs with unpaid penalties are determined to be connected; and selecting network links corresponding to at least some edges identified in the network solution to include in the minimum cost network.