A Set of Inverse Telecommunication Network Problems

Abstract:

In this paper, we consider a set of inverse telecommunication network problem under norm. With the expansion of telecommunication network, more and more links and nodes will be added to the existed telecommunication network. The original network can not cover new nodes and some old links become useless. The telecommunication company wants to sell some old links and purchase some new links within a given budget, such that the network of the company is able to access all nodes. We consider the inverse problem by using weakly dominant set, which is to change the weights of the edges as little as possible such that the given edge set becomes a weakly dominant set under the new weights. In this paper, we propose a polynomial time algorithm for the inverse problem under norm, and we also present an example to illustrate the algorithm.

• Periodical: Advanced Materials Research (Volumes 760-762)
• Pages: 665-668
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.760-762.665
• Online since: September 2013
• Authors: Zhe Heng Ding, Jing Wang, Qin Wang
• Keywords: Inverse Problem, Telecommunication Network, Weakly Dominant Set

References

[1] Q. Wang, X.G. Yang, J.Z. Zhang. A class of inverse dominant problem under weighted norm and an improved complexity bound for Radzik's Algorithm. Journal of Global Optimization, 34: 551-567, (2006).

DOI: 10.1007/s10898-005-1649-y

[2] D. Burton and Ph.L. Toint, On an instance of the inverse shortest paths problem, Mathematical Programming, 53: 45–61, (1992).

DOI: 10.1007/bf01585693

[3] P.T. Sokkalingam, R.K. Ahuja and J.B. Orlin, Solving inverse spanning tree problems through network flow techniques, Operation Research, 47 (2): 291-298, (1999).

DOI: 10.1287/opre.47.2.291

[4] R.K. Ahuja, J.B. Orlin, A faster algorithm for the inverse spanning tree problem, Journal of Algorithms, 34: 177-193, (2000).

DOI: 10.1006/jagm.1999.1052

[5] C. Heuberger, Inverse optimization, a survey on problems, methods, and results, Journal of Combinatorial Optimization, 8: 329-361, (2004).

DOI: 10.1023/b:joco.0000038914.26975.9b

[6] J.Z. Zhang, Z.H. Liu, A general model of some inverse combinatorial optimization problems and its solution method under norm. Journal of Combinatorial Optimization, 6: 207-227, (2002).