Approximation algorithm for optimal location of concentrators and design of capacitated survivable backbone networks
type: Item
instance of: scholarly article
title: Approximation algorithm for optimal location of concentrators and design of capacitated survivable backbone networks
zbMATH Open document ID: 1204.90016
DOI: 10.1504/IJMOR.2011.037311
author: Arun Jotshi
author: Sarat Puthenpura
author: Wenjie Zhao
published in: International Journal of Mathematics in Operational Research
publication date: 2011-02-04T00:00:00Z
review text: Summary: We focus on the problem of selecting concentrator locations to minimise the access network costs. This falls under the general class of Uncapacitated Facility Location (UFL) problem. We present an approximation algorithm along with some computational results. We also study the problem of designing a Capacitated Survivable Backbone Network (CSBN) with the property that there is at least one route present between all the communicating node pairs in the case of a single link failure. Mathematical formulation to efficiently solve the survivable backbone network design problem is presented. The methodologies developed are applied to a real world setting obtaining optimal or near-optimal results.
Mathematics Subject Classification ID: 90B10
Mathematics Subject Classification ID: 90B80
zbMATH DE Number: 5845422
zbMATH Keywords: facility location
zbMATH Keywords: access networks
zbMATH Keywords: survivable backbone networks
zbMATH Keywords: capacitated backbone networks
zbMATH Keywords: \(k\)-connected networks
zbMATH Keywords: concentrator locations
zbMATH Keywords: network costs
zbMATH Keywords: link failure
zbMATH Keywords: network design
MaRDI profile type: Publication
full work available at URL: ijmor.2011.037311
OpenAlex ID: W2027010846
description: scientific article; zbMATH DE number 5845422