Abstract
Quality of Service (QoS) Routing problem has been attracting considerable attention thanks to the rapid development of the high-speed communication network, image processing and computer science. In the past decades, many Quality of Service Routing algorithms were presented based on the QoS requirements and the resource constraints.
The idea of the inverse optimization problem is to modify the given or estimated parameters such that the given feasible solution became an optimal solution. The modification costs are measured by different norms, such as \(l_1\) norm, \(l_2\) norm, \(l_\infty \) norm, Hamming distance and so on.
In this paper, we consider the inverse multicast quality of service routing problems under the weighted \(l_1\) norm. We present combinatorial algorithms which can be finished in strongly polynomial time.
This research is supported by the National Natural Science Foundation of China (Grant No. 11001232, 61301098), Fujian Provincial Natural Science Foundation of China (Grant No. 2012J01021) and Fundamental Research Funds for the Central Universities (Grant No. 20720160035, 20720150002).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Ahuja, R.K., Orlin, J.B.: Combinatorial algorithms for inverse network flow problems. Networks 40, 181–187 (2002)
Berman, O., Ingco, D.I., Odoni, A.: Improving the location of minimax facilities through network modification. Networks 24, 31–41 (1994)
Burton, D., Toint, P.L.: On an instance of the inverse shortest paths problem. Math. Program. 53, 45–61 (1992)
Chen, S.G., Nahrsted, K.: An overview of quality of serice routing for next-generation high-speed networks: problems and solutions. IEEE Netw., Special Issue Transm. Distrib. Digit. Video 12(6), 64–79 (1998)
Güler, C., Hamacher, H.W.: Capacity inverse minimum cost flow problem. J. Comb. Optim. 19, 43–59 (2010)
Heuberger, C.: Inverse optimization: a survey on problems, methods, and results. J. Comb. Optim. 8, 329–361 (2004)
Liu, L.C., Yao, E.Y.: A weighted inverse minimum cut problem under the bottleneck type Hamming distance. Asia. Pac. J. Oper. Res. 24, 725–736 (2007)
Orlin, J.B.: Max flows in \(O(nm)\) time, or better. In: Proceedings of STOC 2013, pp. 765–774 (2013)
Tayyebi, J., Aman, M.: Note on “Inverse minimum cost flow problems under the weighted Hamming distance”. Eur. J. Oper. Res. 234, 916–920 (2014)
Yang, C., Zhang, J.Z., Ma, Z.F.: Inverse maximum flow and minimum cut problems. Optimization 40, 147–170 (1997)
Zhang, J.Z., Cai, M.C.: Inverse problem of minimum cuts. Math. Method. Oper. Res. 47, 51–58 (1998)
Zhang, J.Z., Liu, Z.H., Ma, Z.F.: Some reverse location problems. Eur. J. Oper. Res. 124, 77–88 (2000)
Zhang, J.Z., Ma, Z.F., Yang, C.: A column generation method for inverse shortest path problems. ZOR-Math. Method. Oper. Res. 41, 347–358 (1995)
Zhang, B.W., Zhang, J.Z., He, Y.: The center location improvement problem under the Hamming distance. J. Comb. Optim. 9, 187–198 (2005)
Zhang, B.W., Zhang, J.Z., Qi, L.Q.: The shortest path improvement problems under Hamming distance. J. Comb. Optim. 12, 351–361 (2006)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 ICST Institute for Computer Sciences, Social Informatics and Telecommunications Engineering
About this paper
Cite this paper
Liu, L., Chen, Y., Zheng, W., Wang, D. (2017). Inverse Multicast Quality of Service Routing Problem with Bandwidth and Delay Under the Weighted \(l_1\) Norm. In: Guo, S., Wei, G., Xiang, Y., Lin, X., Lorenz, P. (eds) Testbeds and Research Infrastructures for the Development of Networks and Communities. TridentCom 2016. Lecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering, vol 177. Springer, Cham. https://doi.org/10.1007/978-3-319-49580-4_15
Download citation
DOI: https://doi.org/10.1007/978-3-319-49580-4_15
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-49579-8
Online ISBN: 978-3-319-49580-4
eBook Packages: Computer ScienceComputer Science (R0)