On the cycle polytope of a binary matroid
type: Item
instance of: scholarly article
title: On the cycle polytope of a binary matroid
zbMATH Open document ID: 0596.05018
DOI: 10.1016/0095-8956(86)90063-8
published in: Journal of Combinatorial Theory. Series B
publication date: 1986-01-01T00:00:00Z
review text: Linear optimization problems defined over the polytope \(P(M,b)=conv\{x\in \{0,1\}^ n:\) Mx\(\equiv b\) (mod 2)\(\}\) are often used in modelling real world problems. The following results regarding P(M,b) are shown: (1) In order to characterize the facet defining inequalities of P(M,b) it is enough to characterize the facets that contain a given vertex. As a corollary it can be shown that P(M,b) is defined by the so-called cocircuit-inequalities. (2) Adjacency on P(M,b) is characterized. (3) The Hirsch conjecture is proved if the binary matroid associated with M contains on \(F^*_ 7\) minor.
Mathematics Subject Classification ID: 05B35
Mathematics Subject Classification ID: 90C05
zbMATH DE Number: 3959447
zbMATH Keywords: polyhedral combinatorics
zbMATH Keywords: binary matroid
author: Francisco Barahona
author: Martin Grötschel
reviewed by: Horst W. Hamacher
MaRDI profile type: Publication
full work available at URL: 0095-8956(86)90063-8
OpenAlex ID: W2034664894
cites work: The max-cut problem on graphs not contractible to \(K_ 5\)
cites work: Maximum matching and a polyhedron with 0,1-vertices
cites work: Q5675543
cites work: Matching, Euler tours and the Chinese postman
cites work: Binary group and Chinese postman polyhedra
cites work: Adjacency on the Postman Polyhedron
cites work: Some polyhedra related to combinatorial problems
cites work: Q3330973
cites work: Matroids and multicommodity flows
cites work: Q4111952
description: scientific article; zbMATH DE number 3959447