|
|
|
| New Discoveries of Domination Between Traffic Matrices |
| Peng-fei LIU1, Wen-guo YANG1,2, Tian-de GUO1,2 |
1 School of Mathematics Sciences, University of Chinese Academy of Sciences, Beijing 100049, China;
2 Key Laboratory of Big Data Mining and Knowledge Management, Chinese Academy of Sciences, Beijing 100049, China |
|
|
|
|
Abstract In this paper the definition of domination is generalized to the case that the elements of the traffic matrices may have negative values. It is proved that D3 dominates D3 + λ(D2 -D1) for any λ > 0 if D1 dominates D2. Let U(D) be the set of all the traffic matrices that are dominated by the traffic matrix D. It is shown that U(D∞) and U(D∈) are isomorphic. Besides, similar results are obtained on multi-commodity flow problems. Furthermore, the results are the generalized to integral flows.
|
|
Received: 25 January 2015
|
|
|
| Fund:Supported by National Natural Science Foundation of China under Grant No.(1157101511331012), the Open Project of Key Laboratory of Big Data Mining and Knowledge Management and Knowledge Innovation Program of the Chinese Academy of Sciences under Grant No.(KGCX2-RW-329). |
| About author:: 90B10 |
|
|
|
| [1] |
Ben-Ameur, W., Kerivin, H. Routing of uncertain traffic demands. Optimization and Engineering, 6(3):283-313(2005)
|
| [2] |
Bertsimas, D., Sim, M. Robust discrete optimization and network flows. Mathematical Programming, 98(1-3):49-71(2003)
|
| [3] |
Chekuri, C., Shepherd, F.B., Oriolo, G., et al. Hardness of robust network design. Networks, 50(1):50-54(2007)
|
| [4] |
Duffield, N.G., Goyal, P., Greenberg, A., et al. A flexible model for resource management in virtual private networks. ACM SIGCOMM Computer Communication Review. ACM, 29(4):95-108(1999)
|
| [5] |
Fingerhut, J.A., Suri, S. Turner, J.S. Designing least-cost nonblocking broadband networks. Journal of Algorithms, 24(2):287-309(1997)
|
| [6] |
Gupta, A., Kleinberg, J., Kumar, A., et al. Provisioning a virtual private network:a network design problem for multicommodity flow. Proceedings of the thirty-third annual ACM symposium on theory of computing, ACM, 2001, 389-398
|
| [7] |
Iri, M. On an extension of the max-flow min-cut theorem for multicommodity flows. J. Oper. Res. Soc. Japan, 13:129-135(1970)
|
| [8] |
Onaga, K., Kakusho, O. On feasibility conditions of multicommodity flows in networks. Circuit Theory, IEEE Transactions on, 18(4):425-429(1971)
|
| [9] |
Oriolo, G. Domination between traffic matrices. Mathematics of Operations Research, 33(1):91-96(2008)
|
|
|
|
2017, Vol. 33 
