On matroid parity and matching polytopes

作     者：Kaparis, Konstantinos Letchford, Adam N. Mourtos, Ioannis 

作者机构：Univ Macedonia Dept Business Adm Thessaloniki 54006 Greece Univ Lancaster Dept Management Sci Lancaster LA1 4YX England Athens Univ Econ & Business Dept Management Sci & Technol Athens 10434 Greece 

出 版 物：《DISCRETE APPLIED MATHEMATICS》 (离散应用数学)

年 卷 期：2020年第284卷

页      面：322-331页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

基　　金：Athens University of Economics and Business  Greece through its Basic Research Funding Program 

主　　题：Matroid parity Matroid matching Polyhedral combinatorics 

摘      要：The matroid parity (MP) problem is a powerful (and NP-hard) extension of the matching problem. Whereas matching polytopes are well understood, little is known about MP polytopes. We prove that, when the matroid is laminar, the MP polytope is affinely congruent to a perfect b-matching polytope. From this we deduce that, even when the matroid is not laminar, every Chvatal-Gomory cut for the MP polytope can be derived as a {0, 1/2}-cut from a laminar family of rank constraints. We also prove a negative result concerned with the integrality gap of two linear relaxations of the MP problem. (C) 2020 Elsevier B.V. All rights reserved.