Ghasvari, H.; Raayatpanah, M. A.; Pardalos, P. M. A robust optimization approach for multicast network coding under uncertain link costs. (English) Zbl 1369.90033 Optim. Lett. 11, No. 2, 429-444 (2017). Summary: Network coding is a technique that can be used to improve the performance of communication networks by performing mathematical operations at intermediate nodes. An important problem in coding theory is that of finding an optimal coding subgraph for delivering network data from a source node throughout intermediate nodes to a set of destination nodes with the minimum transmission cost. However, in many real applications, it can be difficult to determine exact values or specific probability distributions of link costs. Establishing minimum-cost multicast connections based on erroneous link costs might exhibit poor performance when implemented. This paper considers the problem of minimum-cost multicast using network coding under uncertain link costs. We propose a robust optimization approach to obtain solutions that protect the system against the worst-case value of the uncertainty in a prespecified set. The simulation results show that a robust solution provides significant improvement in worst-case performance while incurring a small loss in optimality for specific instances of the uncertainty. Cited in 2 Documents MSC: 90B18 Communication networks in operations research 90C47 Minimax problems in mathematical programming Keywords:network coding; multicast; robust optimization PDFBibTeX XMLCite \textit{H. Ghasvari} et al., Optim. Lett. 11, No. 2, 429--444 (2017; Zbl 1369.90033) Full Text: DOI References: [1] Ahlswede, R., Cai, N., Li, S.Y.R., Yeung, R.W.: Network information flow. IEEE Trans. Inf. Theory 46(4), 1204-1216 (2000) · Zbl 0991.90015 · doi:10.1109/18.850663 [2] Li, S.Y.R., Yeung, R.W., Cai, N.: Linear network coding. IEEE Trans. Inf. Theory 49(2), 371-381 (2003) · Zbl 1063.94004 · doi:10.1109/TIT.2002.807285 [3] Jaggi, S., Sanders, P., Chou, P.A., Effros, M., Egner, S., Jain, K., Tolhuizen, L.M.G.M.: Polynomial time algorithms for multicast network code construction. IEEE Trans. Inf. Theory 51(6), 1973-1982 (2005) · Zbl 1288.94098 · doi:10.1109/TIT.2005.847712 [4] Koetter, R., Médard, M.: An algebraic approach to network coding. IEEE/ACM Trans. Netw. 11(5), 782-795 (2003) · doi:10.1109/TNET.2003.818197 [5] Lun, D.S., Ratnakar, N., Médard, M., Koetter, R., Karger, D.R., Ho, T., Ahmed, E., Zhao, F.: Minimum-cost multicast over coded packet networks. IEEE Trans. Inf. Theory 52(6), 2608-2623 (2006) · Zbl 1317.94010 · doi:10.1109/TIT.2006.874523 [6] Oliveira, C.A.S., Pardalos, P.M.: Mathematical Aspects of Network Routing Optimization. Springer, Berlin (2011) · Zbl 1225.90002 · doi:10.1007/978-1-4614-0311-1 [7] Raayatpanah, M.A., Salehi Fathabadi, H., Khalaj, B.H., Khodayifar, S.: Minimum cost multiple multicast network coding with quantized rates. Comput. Netw. 57, 1113-1123 (2012) · Zbl 1252.90013 · doi:10.1016/j.comnet.2012.11.017 [8] Raayatpanah, M.A., Salehi Fathabadi, H., Khalaj, B.H., Khodayifar, S., Pardalos, P.M.: Bounds on end-to-end statistical delay and jitter in multiple multicast coded packet networks. J. Netw. Comput. Appl. 41, 217-227 (2014) · doi:10.1016/j.jnca.2013.12.004 [9] Dantzig, G.B.: Linear programming under uncertainty. In: Infanger, G. (ed.) Stochastic Programming, pp. 1-11. Springer, New York (2011) · Zbl 1215.90042 [10] Birge, J.R., Louveaux, F.: Introduction to Stochastic Programming. Springer, Berlin (2011) · Zbl 1223.90001 · doi:10.1007/978-1-4614-0237-4 [11] Soyster, A.L.: Convex programming with set-inclusive constraints and applications to inexact linear programming. Oper. Res. 21(5), 1154-1157 (1973) · Zbl 0266.90046 · doi:10.1287/opre.21.5.1154 [12] Falk, J.E.: Exact solutions of inexact linear programs. Oper. Res. 24(4), 783-787 (1976) · Zbl 0335.90035 · doi:10.1287/opre.24.4.783 [13] Ben-Tal, A., Nemirovski, A.: Robust convex optimization. Math. Oper. Res. 23(4), 769-805 (1998) · Zbl 0977.90052 · doi:10.1287/moor.23.4.769 [14] Ben-Tal, A., Nemirovski, A.: Robust solutions of uncertain linear programs. Oper. Res. Lett. 25(1), 1-13 (1999) · Zbl 0941.90053 · doi:10.1016/S0167-6377(99)00016-4 [15] Ben-Tal, A., Nemirovski, A.: Robust solutions of linear programming problems contaminated with uncertain data. Math. Program. 88(3), 411-424 (2000) · Zbl 0964.90025 · doi:10.1007/PL00011380 [16] El Ghaoui, L., Oustry, F., Lebret, H.: Robust solutions to uncertain semidefinite programs. SIAM J. Optim. 9(1), 33-52 (1998) · Zbl 0960.93007 · doi:10.1137/S1052623496305717 [17] Bertsimas, D., Sim, M.: The price of robustness. Oper. Res. 52(1), 35-53 (2004) · Zbl 1165.90565 · doi:10.1287/opre.1030.0065 [18] Fan, N., Pardalos, P.M.: Robust optimization of graph partitioning and critical node detection in analyzing networks. In: Wu, W., Daescu, O. (eds.) Combinatorial Optimization and Applications, pp. 170-183. Springer, Berlin (2010) · Zbl 1311.90163 [19] Fan, N., Zheng, Q.P., Pardalos, P.M.: Robust optimization of graph partitioning involving interval uncertainty. Theor. Comput. Sci. 447, 53-61 (2012) · Zbl 1245.05101 · doi:10.1016/j.tcs.2011.10.015 [20] Georgiev, G.P., Luc, D.T., Pardalos, P.M.: Robust aspects of solutions in deterministic multiple objective linear programming. Eur. J. Oper. Res. 229(1), 29-36 (2013) · Zbl 1317.90262 · doi:10.1016/j.ejor.2013.02.037 [21] Xanthopoulos, P., Guarracino, M.R., Pardalos, P.M.: Robust generalized eigenvalue classifier with ellipsoidal uncertainty. Ann. Oper. Res. 216(1), 327-342 (2014) · Zbl 1296.90084 · doi:10.1007/s10479-012-1303-2 [22] Xanthopoulos, P., Pardalos, P., Trafalis, T.B.: Robust Data Mining. Springer, Berlin (2012) · Zbl 1260.90003 [23] Xi, Y., Yeh, E.M.: Distributed algorithms for minimum cost multicast with network coding. IEEE/ACM Trans. Netw. 18(2), 379-392 (2010) · doi:10.1109/TNET.2009.2026275 [24] Bazaraa, M.S., Jarvis, J.J., Sherali, H.D.: Linear Programming and Network Flows. Wiley-Interscience, New York (2011) · Zbl 1200.90002 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.