On the Maximum-Weight Basis Problem

Publication date 15 June 2016

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27) Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40)

Abstract: Let M to be a matroid defined on a finite set E. A subset L of E is locked in M if L is 2-connected in M, the complement of L is 2-connected in the dual M*, and min{r(L), r*(complement of L)} is greater than 1. In this paper, we prove that the nontrivial facets of the bases polytope of M are described by the locked subsets. We deduce that finding the maximum-weight basis of M is a polynomial problem for matroids with a polynomial number of locked subsets. This class of matroids is closed under 2-sums and contains uniform matroids.

This page was built for publication: On the Maximum-Weight Basis Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6274713)