On the inverse maximum perfect matching problem under the bottleneck-type Hamming distance

Document Type : Original paper

Author

Birjand university of technology

Abstract

Given an undirected network $G(V,A,c)$ and a perfect matching $M$ of $G$, the inverse maximum perfect matching problem consists of modifying minimally the elements of c so that M becomes a maximum perfect matching with respect to the modified vector. In this article, we consider the inverse problem when the modifications are measured by the weighted bottleneck-type Hamming distance. We propose an algorithm based on the binary search technique for solving the problem. Our proposed algorithm has a better time complexity than the one presented in [13]. We also study the inverse assignment problem as a special case of the inverse maximum perfect matching problem in which the network is bipartite and present an efficient algorithm for solving the problem. Finally, we compare the algorithm with those presented in the literature.

Keywords

Main Subjects

References

[1] R.K. Ahuja, T.L. Magnanti, and J.B. Orlin, Network flows, Prentice-Hall, Englewood Cliffs, 1993.
[2] M. Aman and J. Tayyebi, Capacity inverse minimum cost flow problem under the weighted hamming distances, Iranian Journal of Operations Research 5 (2014), no. 2, 12–25.
[3] M.S. Bazaraa and J. Jarvis, Linear programming and network flows, Wiley, New York, 1997.
[4] C. Berge, Two theorems in graph theory, Proceedings of the National Academy of Sciences 43 (1957), no. 9, 842–844.
[5] M. Demange and J. Monnot, An introduction to inverse combinatorial problems, in: Paradigms of combinatorial optimization (problems and new approaches), Wiley, London-Hoboken (UK-USA), Vangelis Th. Paschos, 2010, 547–586.
[6] C.W. Duin and A. Volgenant, Some inverse optimization problems under the hamming distance, European J. Oper. Res. 170 (2006), no. 3, 887–899.
[7] J. Edmonds, Maximum matching and a polyhedron with 0, 1-vertices, J. Res. Natl. Bureau Stand. B 69B (1965), no. 1-2, 125–130.
[8] Y. He, B. Zhang, and E. Yao, Weighted inverse minimum spanning tree problems under hamming distance, J. Comb. Optim. 9 (2005), no. 1, 91–100.
[9] Y. Jiang, L. Liu, B. Wu, and E. Yao, Inverse minimum cost flow problems under the weighted hamming distance, European J. Oper. Res. 207 (2010), no. 1, 50–54.
[10] E.L. Lawler, Combinatorial optimization: Networks and matroids, Holt, Rinehart and Winston, New York, 1976.
[11] L. Liu and Q. Wang, Constrained inverse min–max spanning tree problems under the weighted hamming distance, J. Global Optim. 43 (2009), no. 1, 83–95.
[12] L. Liu and E. Yao, Inverse minmax spanning tree problem under the weighted sum-type hamming distance, Theoret. Comput. Sci. 396 (2008), 28–34.
[13] L. Liu and E. Yao, Weighted inverse maximum perfect matching problems under the hamming distance, J. Global Optim. 55 (2013), no. 3, 549–557.
[14] Z. Liu and J. Zhang, On inverse problems of optimum perfect matching, J. Comb. Optim. 7 (2003), no. 3, 215–228.
[15] J. Roland, Y.D. Smeta, and J. Figueira, Inverse multi-objective combinatorial optimization, Discrete Appl. Math. 161 (2013), no. 16-17, 2764–2771.
[16] J. Tayyebi and M. Aman, Note on“inverse minimum cost flow problems under the weighted hamming distance”, European J. Oper. Res. 234 (2014), no. 3, 916–920.
[17] J. Tayyebi and M. Aman, On inverse linear programming problems under the bottleneck-type weighted hamming distance, Discrete Appl. Math. 240 (2018), 92–101.
Communications in Combinatorics and Optimization
Volume 4, Issue 1
June 2019
Pages 35-46

Files

Share

How to cite

Statistics