Abstract
Given an undirected network G(V, E, c) and a perfect matching M 0, the inverse maximum perfect matching problem is to modify the cost vector as little as possible such that the given perfect matching M 0 can form a maximum perfect matching. The modification can be measured by different norms. In this paper, we consider the weighted inverse maximum perfect matching problems under the Hamming distance, where we use the weighted Hamming distance to measure the modification of the edges. We consider both of the sum-type and the bottleneck-type problems. For the general case of the sum-type case, we show it is NP-hard. For the bottleneck-type, we present a strongly polynomial algorithm which can be done in O(m · n 3).
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Berge C.: Two theorems in graph theory. Proc. Natl. Acad. Sci. USA 43, 842–844 (1957)
Demange, M., Monnot, J.: An introduction to inverse combinatorial problems. In: Paradigms of Combinatorial Optimization (Problems and New approaches), pp. 547–586. Wiley, London-Hoboken (UK-USA), Vangelis Th. Paschos (2010)
Edmonds J.: Maximum matching and a polyhedron with 0-1 vertices. J. Res. Natl. Bureau Stand. 69, 125–130 (1965)
He Y., Zhang B.W., Yao E.Y.: Weighted inverse minimum spanning tree problems under Hamming distance. J. Comb. Optim. 9, 91–100 (2005)
Heuberger C.: Inverse optimization: a survey on problems, methods, and results. J. Comb. Optim. 8, 329–361 (2004)
Lawler E.L.: Combinatorial Optimization: Networks and Matroids Holt. Rinehart and Winston, New York (1976)
Liu L.C., He Y.: Inverse minimum spanning tree problem and reverse shortest-path problem with discrete values. Prog. Nat. Sci. 16(6), 649–655 (2006)
Liu L.C., Wang Q.: Constrained inverse min–max spanning tree problems under the weighted Hamming distance. J. Glob. Optim. 43, 83–95 (2009)
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)
Liu L.C., Yao E.Y.: Inverse min–max spanning tree problem under the weighted sum-type Hamming distance. Theor. Comp. Sci. 396, 28–34 (2008)
Liu L.C., Zhang J.Z.: Inverse maximum flow problems under the weighted Hamming distance. J. Comb. Optim. 12, 395–408 (2006)
Liu Z.H., Zhang J.Z.: On inverse problems of optimum perfect matching. J. Comb. Optim. 7, 215–228 (2003)
Yang X.G., Zhang J.Z.: Inverse sorting problem by minimizing the total weighted number of changes and partial inverse sorting problems. Comp. Optim. Appl. 36, 55–66 (2007)
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., He Y.: Constrained inverse minimum spanning tree problems under the bottleneck-type Hamming distance. J. Glob. Optim. 34, 467–474 (2006)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Liu, L., Yao, E. Weighted inverse maximum perfect matching problems under the Hamming distance. J Glob Optim 55, 549–557 (2013). https://doi.org/10.1007/s10898-012-9901-8
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10898-012-9901-8