×

On the complexity of the regenerator cost problem in general networks with traffic grooming. (English) Zbl 1360.68507

Summary: In a communication network one often needs to combine several communication requests into a path in a physical layer of the network. In these cases the cost is measured in terms of the total length of these paths or the total hardware cost of maintaining these paths. In this paper we consider a problem belonging to this general family of optimization problems. 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 \(\mathrm{P}=\mathrm{NP}\)). On the other hand, we solve such a problem for general \(G\) and any \(d\) and \(g\), by providing an \(O (\log g)\)-approximation algorithm and thus extending previous results holding only for specific topologies and specific values of \(d\) or \(g\).

MSC:

68Q25 Analysis of algorithms and problem complexity
68M10 Network design and communication in computer systems
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
68W25 Approximation algorithms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Amini, O., Pérennes, S., Sau, I.: Hardness and approximation of traffic grooming. Theor. Comput. Sci. 410(38-40), 3751-3760 (2009) · Zbl 1171.68049 · doi:10.1016/j.tcs.2009.04.028
[2] Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.: Complexity and Approximation, Combinatorial Optimization Problems and Their Approximability Properties. Springer, Berlin (1999) · Zbl 0937.68002
[3] Chen, S., Ljubić, I., Raghavan, S.: The regenerator location problem. Networks 55(3), 205-220 (2010) · Zbl 1200.90113
[4] Chvátal, V.: A greedy heuristic for the set covering problem. Math. Oper. Res. 4, 233-235 (1979) · Zbl 0443.90066 · doi:10.1287/moor.4.3.233
[5] Călinescu, G., Frieder, O., Wan, P.-J.: Minimizing electronic line terminals for automatic ring protection in general WDM optical networks. IEEE J. Sel. Areas Commun. 20(1), 183-189 (2002) · doi:10.1109/49.974672
[6] Călinescu, G., Wan, P.-J.: Splitable traffic partition in WDM/SONET rings to minimize sonet ADMs. Theor. Comput. Sci. 276(1-2), 33-50 (2002) · Zbl 1016.68002 · doi:10.1016/S0304-3975(01)00101-3
[7] Călinescu, G., Wan, P.-J.: Traffic partition in WDM/SONET rings to minimize SONET ADMs. J. Comb. Optim. 6(4), 425-453 (2002) · Zbl 1046.90012 · doi:10.1023/A:1019525904862
[8] Saradhi, C. V.; Zanardi, A.; Fedrizzi, R.; Salvadori, E.; Galimberti, G. M.; Tanzi, A.; Martinelli, G.; Gerstel, O., A framework for regenerator site selection based on multiple paths, 1-3 (2010), New York
[9] Flammini, M., Marchetti-Spaccamela, A., Monaco, G., Moscardelli, L., Zaks, S.: On the complexity of the regenerator placement problem in optical networks. IEEE/ACM Trans. Netw. 19(2), 498-511 (2011) · doi:10.1109/TNET.2010.2068309
[10] Flammini, M., Monaco, G., Moscardelli, L., Shachnai, H., Shalom, M., Tamir, T., Zaks, S.: Minimizing total busy time in parallel scheduling with application to optical networks. Theor. Comput. Sci. 411(40-42), 3553-3562 (2010) · Zbl 1207.68110 · doi:10.1016/j.tcs.2010.05.011
[11] Flammini, M.; Monaco, G.; Moscardelli, L.; Shalom, M.; Zaks, S., Approximating the traffic grooming problem with respect to ADMs and OADMs, No. 5168, 920-929 (2008), Berlin
[12] Flammini, M., Monaco, G., Moscardelli, L., Shalom, M., Zaks, S.: Optimizing regenerator cost in traffic grooming. Theor. Comput. Sci. 412(52), 7109-7121 (2011) · Zbl 1229.90032 · doi:10.1016/j.tcs.2011.09.023
[13] Gerstel, O.; Lin, P.; Sasaki, G., Wavelength assignment in a WDM ring to minimize cost of embedded sonet rings, 69-77 (1998), Providence
[14] Khandekar, R.; Schieber, B.; Shachnai, H.; Tamir, T., Minimizing busy time in multiple machine real-time scheduling, Schloss Dagstuhl · Zbl 1245.68038
[15] Mertzios, G.B., Sau, I., Shalom, M., Zaks, S.: Placing regenerators in optical networks to satisfy multiple sets of requests. IEEE/ACM Trans. Netw. (2012). doi:10.1109/TNET.2012.2186462 · Zbl 1288.68014 · doi:10.1109/TNET.2012.2186462
[16] Sriram, K.; Griffith, D.; Su, R.; Golmie, N., Static vs. dynamic regenerator assignment in optical switches: models and cost trade-offs, 151-155 (2004), New York
[17] Vazirani, V.V.: Approximation Algorithms. Springer, Berlin (2004) · Zbl 1005.68002
[18] Winkler, P.; Zhang, L., Wavelength assignment and generalized interval graph coloring, 830-831 (2003), New York · Zbl 1092.68635
[19] Yang, X., Ramamurthy, B.: Sparse regeneration in translucent wavelength-routed optical networks: architecture, network design and wavelength routing. Photonic Netw. Commun. 10(1), 39-53 (2005) · doi:10.1007/s11107-005-1694-y
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.