On Inverse Problems of Optimum Perfect Matching

Zhenhong Liu and Jianzhong Zhang ()
Additional contact information
Zhenhong Liu: Institute of Systems Science, Academia Sinica
Jianzhong Zhang: City University of Hong Kong

Journal of Combinatorial Optimization, 2003, vol. 7, issue 3, No 1, 215-228

Abstract: Abstract As far as we know, for most polynomially solvable network optimization problems, their inverse problems under l 1 or l ∞ norm have been studied, except the inverse maximum-weight matching problem in non-bipartite networks. In this paper we discuss the inverse problem of maximum-weight perfect matching in a non-bipartite network under l 1 and l ∞ norms. It has been proved that the inverse maximum-weight perfect matching under l ∞ norm can be formulated as a maximum-mean alternating cycle problem of an undirected network, and can be solved in polynomial time by a binary search algorithm and in strongly polynomial time by an ascending algorithm, and under l 1 norm it can be solved by the ellipsoid method. Therefore, inverse problems of maximum-weight perfect matching under l 1 and l ∞ norms are solvable in polynomial time.

Keywords: maximum-weight matching; perfect matching; maximum-mean alternating cycle; ellipsoid method; strongly polynomial algorithm; linear programming (search for similar items in EconPapers)
Date: 2003
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://link.springer.com/10.1023/A:1027305419461 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:7:y:2003:i:3:d:10.1023_a:1027305419461

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1023/A:1027305419461

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().