For k=2 and 3, the authors define several k-sums of binary matroids and of polytopes arising from cycles of binary matroids. They then establish relationships between these k-sums, and use these results to give a direct proof that a certain LP-relaxation of the cycle polytope is the polytope itself if and only if M does not have certain minors. The latter theorem was proved earlier by Barahona and Grötschel via Seymour’s deep theorem characterizing the matroids with the sum of circuits property. The authors also exploit the relationships between matroid and polytope k-sums to construct polynomial time algorithms for the solution of the maximum weight cycle problem for some classes of binary matroids and for the solution of the separation problem of the LP-relaxation mentioned above.
