We consider the problem of minimizing the number of regenerators in optical networks with traffic grooming. In this problem we are given a network with an underlying topology of a graph G, a set of requests that correspond to paths in G and two positive integers g and d. There is a need to put a regenerator every d edges of every path, because of a degradation in the quality of the signal. Each regenerator can be shared by at most g paths, g being the grooming factor. On the one hand, we show that even in the case of d = 1 the problem is APX - hard, i.e. a polynomial time approximation scheme for it does not exist (unless P = NP). On the other hand, we solve such a problem for general G and any d and g, by providing an 0(log g)-approximation algorithm and thus extending previous results holding only for specific topologies and specific values of d or g.
On the Complexity of the Regenerator Cost Problem in General Networks with Traffic Grooming
MOSCARDELLI, Luca;Monaco, Gianpiero
2011-01-01
Abstract
We consider the problem of minimizing the number of regenerators in optical networks with traffic grooming. In this problem we are given a network with an underlying topology of a graph G, a set of requests that correspond to paths in G and two positive integers g and d. There is a need to put a regenerator every d edges of every path, because of a degradation in the quality of the signal. Each regenerator can be shared by at most g paths, g being the grooming factor. On the one hand, we show that even in the case of d = 1 the problem is APX - hard, i.e. a polynomial time approximation scheme for it does not exist (unless P = NP). On the other hand, we solve such a problem for general G and any d and g, by providing an 0(log g)-approximation algorithm and thus extending previous results holding only for specific topologies and specific values of d or g.File | Dimensione | Formato | |
---|---|---|---|
I29.pdf
Solo gestori archivio
Tipologia:
PDF editoriale
Dimensione
299.86 kB
Formato
Adobe PDF
|
299.86 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.