Skip to Main content Skip to Navigation

Optimal concave costs in the SDH context

Sébastien Choplin 1 Jérôme Galtier Stéphane Pérennes
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : We address a problem of network design with minimum cost, and uniform all-to-all demands between the vertices. We deal with the case of concave increasing link cost function f depending of the capacity over directed arcs. We obtain lower bounds for this problem. In the generic case $f:x\mapsto x^\alpha$, where $\alpha\in[0;1]$, we exhibit some families that constitute an 1.12 asymptotical approximation of the optimal network.
Document type :
Complete list of metadata

Cited literature [1 references]  Display  Hide  Download
Contributor : Rapport de Recherche Inria <>
Submitted on : Friday, May 19, 2006 - 9:39:26 PM
Last modification on : Monday, October 12, 2020 - 10:30:21 AM
Long-term archiving on: : Sunday, April 4, 2010 - 9:55:25 PM


  • HAL Id : inria-00070791, version 1



Sébastien Choplin, Jérôme Galtier, Stéphane Pérennes. Optimal concave costs in the SDH context. RR-5201, INRIA. 2004, pp.11. ⟨inria-00070791⟩



Record views


Files downloads