Weighted restricted 2-matching
成果类型：
Article
署名作者：
Pap, Gyula
署名单位：
Eotvos Lorand University
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-008-0211-3
发表日期：
2009
页码：
305-329
关键词：
摘要：
A perfect 2-matching of a graph is a vector assigning values 0,1, or 2 to the edges such that the sum of values of edges incident with any node is equal to 2. For restricted perfect 2-matchings, we are also given a collection of allowed odd cycles, and restrict ourselves to those perfect 2-matchings the support of which contains no odd cycle not in this collection. Given a graph and a collection of allowed odd cycles, we provide a TDI description of the convex hull of restricted perfect 2-matchings. The description has large coefficients and is given implicitly, thus polynomial time separation or optimization is not straightforward. In order to have such an algorithm, one has to specify the collection of allowed odd cycles. For any fixed number k, we solve optimization in strongly polynomial time for the special cases when the collection consists of odd cycles of length less than k, or odd cycles of length more than k. These solved special cases include minimum weight perfect matching, minimum weight triangle-free and/or pentagon-free perfect perfect 2-matching, and a bunch of other relaxations of the travelling salesman problem. Our algorithm is based on a primal-dual approach, and the unweighted algorithm of Cornu,jols and Hartvigsen, which is used as a subroutine. The TDI description also may be regarded as a generalization of their unweighted min-max formula.