Designing minimum total cost networks using iterative rounding approximation methods
AssigneeAT&T Intellectual Property 1, L.P.
InventorMohammad Hajiaghayi
Life of this patent
Estimating the term…
Loading patent…
AssigneeAT&T Intellectual Property 1, L.P.
InventorMohammad Hajiaghayi
Estimating the term…
Minimum cost networks, such as fiber optic networks used in telecommunications, are obtained by defining available network elements having cost, required pairs, connectivity and penalty cost values and selecting from these available elements using an iterative rounding approximation method that constructs an LP relaxation incorporating the element parameters, finds an optimal basic solution, applies a selection criterion to pairs and edges in the optimal basic solution, and constructs a residual LP relaxation with selected pairs and edges. By fixing selected pairs and edges values to 1 in the residual LP, successive iterations of the method provide a design which is a 3-approximation solution to the minimum cost design problem.
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:
A non-transitory computer-usable medium having computer readable instructions stored thereon for execution by a processor to perform 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, the method comprising:
Dependencies are inferred from the claim text.