Name
Abstract | ||
|---|---|---|
We address a design problem that arises when a circular architecture is adopted to move resources in a system. In many of such architectures the demand directed from one node to another affects all the intermediate nodes, involving costs which increase both with the number of nodes and with the demand volume. We consider an application to network design and propose a model for designing a minimum cost hierarchical ring network. The problem is formalized as that of partitioning a set of nodes into p parts to be connected by rings, with the aim of minimizing the total capacity costs. We prove that the problem is NP-complete for p⩾2 and propose a guaranteed approximation algorithm for the case p=2. We then propose a hybrid approach employing the approximation algorithm in combination with {0,1} LP. Experiments indicate the effectiveness of this approach in terms of computational resources and solution quality. |
Year | DOI | Venue |
|---|---|---|
2000 | 10.1016/S0377-2217(99)00119-8 | European Journal of Operational Research |
Keywords | Field | DocType |
Optimization,Hierarchical ring networks,Computational complexity,Approximation algorithms | Approximation algorithm,Architecture,Mathematical optimization,Network planning and design,Theoretical computer science,Ring network,Optimization problem,Mathematics,Computational complexity theory | Journal |
Volume | Issue | ISSN |
124 | 1 | 0377-2217 |
Citations | PageRank | References |
0 | 0.34 | 4 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Claudio Arbib | 1 | 119 | 22.41 |
| Fabrizio Rossi | 2 | 140 | 16.33 |