Minimum Cost Networks With Redundant Points Of Presence

Abstract

Methods, systems, and products determine minimum cost networks. A k-fold coverage formulation is applied to potential network elements having cost and coverage parameters. Iterative heuristics are used to find an optimal solution to the k-set coverage formulation. The approximate solutions to the k-set coverage formulation are then used to select at least some of the potential network elements for use in a minimum cost network.

1 . A system, comprising:
 a processor; and   memory for storing code that when executed causes the processor to perform operations, the operations comprising:   retrieving a collection of potential network elements, each element in the collection of potential network elements associated with a defined cost value and an object coverage parameter value;   retrieving a k-set coverage formulation for each element in the collection of potential network elements;   retrieving a Langrangian relaxation formulation of the k-set coverage formulation;   applying an iterative subgradient optimization algorithm to the Langrangian relaxation formulation;   iterating the subgradient optimization algorithm to determine an initial solution;   applying a greedy construction algorithm to add selected elements to the initial solution to form a feasible solution by:
 determining unselected elements not selected from the greedy construction algorithm; 
 determining a cardinality of each unselected element in the unselected elements; 
 determining a ratio of cost to the cardinality for each unselected element in the unselected elements; 
 selecting particular ones of the unselected elements based on the ratio of the cost to the cardinality; 
   selecting parameters from the feasible solution for a next iteration of the subgradient optimization algorithm; and   iterating to identify the set of network elements providing the k-fold redundant coverage of objects at the approximate minimum cost.   
     
     
         2 . The system according to  claim 1 , wherein the operations further comprise retrieving a location associated with each element in the collection of potential network elements. 
     
     
         3 . The system according to  claim 1 , wherein the operations further comprise assigning a coverage to each element in the collection of potential network elements. 
     
     
         4 . The system according to  claim 1 , wherein the operations further comprise determining an uncovered network element. 
     
     
         5 . The system according to  claim 1 , wherein the operations further comprise determining a list of candidate network elements. 
     
     
         6 . The system according to  claim 1 , wherein the operations further comprise retrieving a cut-off value for the greedy construction algorithm. 
     
     
         7 . The system according to  claim 1 , wherein the operations further comprise determining a lower cost solution fails to exist. 
     
     
         8 . A memory storing instructions that when executed cause a processor to perform operations, the operations comprising:
 retrieving a collection of potential network elements, each element in the collection of potential network elements associated with a defined cost value and an object coverage parameter value;   retrieving a k-set coverage formulation for each element in the collection of potential network elements;   retrieving a Langrangian relaxation formulation of the k-set coverage formulation;   applying an iterative subgradient optimization algorithm to the Langrangian relaxation formulation;   iterating the subgradient optimization algorithm to determine an initial solution;   applying a greedy construction algorithm to add selected elements to the initial solution to form a feasible solution by:
 determining unselected elements not selected from the greedy construction algorithm; 
 determining a cardinality of each unselected element in the unselected elements; 
 determining a ratio of cost to the cardinality for each unselected element in the unselected elements; 
 selecting particular ones of the unselected elements based on the ratio of the cost to the cardinality; 
   selecting parameters from the feasible solution for a next iteration of the subgradient optimization algorithm; and   iterating to identify the set of network elements providing the k-fold redundant coverage of objects at the approximate minimum cost.   
     
     
         9 . The memory according to  claim 8 , wherein the operations further comprise retrieving a location associated with each element in the collection of potential network elements. 
     
     
         10 . The memory according to  claim 8 , wherein the operations further comprise assigning a coverage to each element in the collection of potential network elements. 
     
     
         11 . The memory according to  claim 8 , wherein the operations further comprise determining an uncovered network element. 
     
     
         12 . The memory according to  claim 8 , wherein the operations further comprise determining a list of candidate network elements. 
     
     
         13 . The memory according to  claim 8 , wherein the operations further comprise retrieving a cut-off value for the greedy construction algorithm. 
     
     
         14 . The memory according to  claim 8 , wherein the operations further comprise determining a lower cost solution fails to exist. 
     
     
         15 . An approximation method for designing a minimum cost network with k-fold redundant coverage of objects to be served by a 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 k-fold redundant coverage of objects at approximate minimum cost, comprising:
 retrieving from memory a k-set coverage formulation with the defined cost value and the object coverage parameter value for each element in the collection of potential network elements;   retrieving from the memory a Langrangian relaxation formulation of the k-set coverage formulation;   applying, by a processor, an iterative subgradient optimization algorithm to the Langrangian relaxation formulation;   determining, by the processor, an initial solution by 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:
 determining unselected elements not selected from the greedy construction algorithm; 
 determining a cardinality of each unselected element in the unselected elements; 
 determining a ratio of cost to the cardinality for each unselected element in the unselected elements; 
 selecting particular ones of the unselected elements based on the ratio of the cost to the cardinality; 
   selecting parameters from the feasible solution for a next iteration of the subgradient optimization algorithm;   iterating to identify the set of network elements providing the k-fold redundant coverage of objects at the approximate minimum cost.   
     
     
         16 . The method according to  claim 15 , further comprising retrieving a location associated with each element in the collection of potential network elements. 
     
     
         17 . The method according to  claim 15 , further comprising assigning a coverage to each element in the collection of potential network elements. 
     
     
         18 . The method according to  claim 15 , further comprising determining an uncovered network element. 
     
     
         19 . The method according to  claim 15 , further comprising determining a list of candidate network elements. 
     
     
         20 . The method according to  claim 15 , further comprising retrieving a cut-off value for the greedy construction algorithm.