Efficient algorithms for the reverse shortest path problem on trees under the hamming distance
DOI:
https://doi.org/10.2298/YJOR150624009TKeywords:
inverse problems, shortest path problem, hamming distance, combinatorial algorithmsAbstract
Given a network G(V,A,c) and a collection of origin-destination pairs with prescribed values, the reverse shortest path problem is to modify the arc length vector c as little as possible under some bound constraints such that the shortest distance between each origin-destination pair is upper bounded by the corresponding prescribed value. It is known that the reverse shortest path problem is NP-hard even on trees when the arc length modifications are measured by the weighted sum-type Hamming distance. In this paper, we consider two special cases of this problem which are polynomially solvable. The first is the case with uniform lengths. It is shown that this case transforms to a minimum cost flow problem on an auxiliary network. An efficient algorithm is also proposed for solving this case under the unit sum-type Hamming distance. The second case considered is the problem without bound constraints. It is shown that this case is reduced to a minimum cut problem on a tree-like network. Therefore, both cases studied can be solved in strongly polynomial time.References
Ahuja, R. K., Magnanti, T. L., and Orlin, J. B., Network Flows, Prentice-Hall, Englewood Cliffs, 1993.
Ahuja, R. K. and Orlin, J. B., “Inverse optimization”, Operations Research, 49 (2001) 771–783.
Burton, D. and Toint, Ph. L., “On an instance of the inverse shortest paths problem”, Mathematical Programming, 53 (1992) 45–61.
Burton, D. and Toint, Ph. L., “On the use of an inverse shortest paths algorithm for recovering linearly correlated costs”, Mathematical Programming, 63 (1994) 1–22.
Burton, D., Pulleyblank, W.R., and Toint, Ph. L., “The inverse shortest path problem with upper bounds on shortest path costs”, In: Pardalos, P., Hearn, D.W., Hager, W.H. (Eds.), Lecture Notes in Economics and Mathematical Systems, Springer, 450 (1997) 156–171.
Call, M., Inverse Shortest Path Routing Problems in the Design of IP Networks, Department of Mathematics, Linköping University, Sweden, 2010.
Cui, T. and Hochbaum, D. S., “Complexity of some inverse shortest path lengths problems”, Networks, 56 (2010) 20–29.
Duin, C.W. and Volgenant, A., “Some inverse optimization problems under the Hamming distance”, European Journal of Operational Research, 170 (2006) 887–899.
Fekete, S.P., Hochstattler, W.H., Kromberg, S. and Moll, C., “The complexity of an inverse shortest paths problem”, Contemporary Trends in Discrete Mathematics: From DIMACS and DIMATIA to the Future, Graham, R.L., Kratochvil, J., Nesetrol, J., Roberts, F.S. (Eds.), American Mathematical Society, DIMATIA-DIMACS Conference, Stirin Castle, Czech Republic, 1997, 49–113.
Gódor, I., Harmatos, J. and Jüttner, A., “Inverse shortest path algorithms in protected UMTS access networks”, Computer Communications, 28 (2005) 765–772.
Heuberger, C., “Inverse optimization: A survey on problems, methods, and results”, Journal of Combinatorial Optimization, 8 (2004) 329–361.
Tayyebi, J. and Aman, M., “On inverse linear programming problems under the bottleneck-type weighted Hamming distance”, Discrete Applied Mathematics, (2015) DOI: 10.1016/j.dam.2015.12.017.
Tayyebi, J. and Aman, M., “Note on inverse minimum cost flow problems under the weighted Hamming distance”, European Journal of Operational Research, 234 (2014) 916–920.
Vygen, J., “On dual minimum cost flow algorithms”, Mathematical Methods of Operations Research, 56 (2002) 101–126.
Xu, S. and Zhang, J., “An Inverse Problem of the Weighted Shortest Path Problem”, Japan Journal of Industrial Applied Mathematics, 12 (1995) 47–59.
Zhang, B. W., Zhang, J. Z. and Qi, L. Q., “The shortest path improvement problems under Hamming distance”, Journal of Combinatorial Optimization, 12 (4) (2006) 351–361.
Zhang, B., Guan, X., He, C. and Wang, S., “Algorithms for the Shortest Path Improvement Problems under Unit Hamming Distance”, Journal of Applied Mathematics, Article ID 847317 (2013) 8 pages.
Downloads
Published
Issue
Section
License
Copyright (c) 2017 YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
