On Inverse Problems of Optimum Perfect Matching

Z. Liu; Jianzhong Zhang

doi:10.1023/A:1027305419461

On Inverse Problems of Optimum Perfect Matching

Z. Liu
, Jianzhong Zhang

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review

13 Citations (Scopus)

Abstract

As far as we know, for most polynomially solvable network optimization problems, their inverse problems under l ₁ 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 ₁ 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 ₁ norm it can be solved by the ellipsoid method. Therefore, inverse problems of maximum-weight perfect matching under l ₁ and l _∞ norms are solvable in polynomial time.
© 2003 Kluwer Academic Publishers

Original language	English
Pages (from-to)	215-228
Journal	Journal of Combinatorial Optimization
Volume	7
Issue number	3
DOIs	https://doi.org/10.1023/A:1027305419461
Publication status	Published - Sept 2003
Externally published	Yes

Bibliographical note

Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].

Funding

∗The research is partially supported by the National Natural Science Foundation of China. †The author gratefully acknowledges the support of Hong Kong University Grant Council under the CERG CityU 1081/99P.

Research Keywords

Ellipsoid method
Linear programming
Maximum-mean alternating cycle
Maximum-weight matching
Perfect matching
Strongly polynomial algorithm

Access Output

10.1023/A:1027305419461

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@article{4802b7e6c3c14ca0a3e68980699f1da1,

title = "On Inverse Problems of Optimum Perfect Matching",

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. {\textcopyright} 2003 Kluwer Academic Publishers",

keywords = "Ellipsoid method, Linear programming, Maximum-mean alternating cycle, Maximum-weight matching, Perfect matching, Strongly polynomial algorithm",

author = "Z. Liu and Jianzhong Zhang",

note = "Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].",

year = "2003",

month = sep,

doi = "10.1023/A:1027305419461",

language = "English",

volume = "7",

pages = "215--228",

journal = "Journal of Combinatorial Optimization",

issn = "1382-6905",

publisher = "Springer Netherlands",

number = "3",

}

TY - JOUR

T1 - On Inverse Problems of Optimum Perfect Matching

AU - Liu, Z.

AU - Zhang, Jianzhong

N1 - Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].

PY - 2003/9

Y1 - 2003/9

N2 - 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. © 2003 Kluwer Academic Publishers

AB - 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. © 2003 Kluwer Academic Publishers

KW - Ellipsoid method

KW - Linear programming

KW - Maximum-mean alternating cycle

KW - Maximum-weight matching

KW - Perfect matching

KW - Strongly polynomial algorithm

UR - https://www.scopus.com/pages/publications/0344012539

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-0344012539&origin=recordpage

U2 - 10.1023/A:1027305419461

DO - 10.1023/A:1027305419461

M3 - RGC 21 - Publication in refereed journal

SN - 1382-6905

VL - 7

SP - 215

EP - 228

JO - Journal of Combinatorial Optimization

JF - Journal of Combinatorial Optimization

IS - 3

ER -

On Inverse Problems of Optimum Perfect Matching

Abstract

Bibliographical note

Funding

Research Keywords

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this