The Facets of the Bases Polytope of a Matroid and Two Consequences

DOI: 10.4236/ojdm.2018.81002, PP. 14-20

Keywords: Bases Polytope, Facets, Locked Subsets, Maximum-Weight Basis Problem, Polynomially Locked Matroids, Matroid Oracle, Testing Unformity of a Matroid

Abstract:

Let M be a matroid defined on a finite set E and L？⊂？E？. L is locked in M if？？and ？are 2-connected, and . In this paper, we prove that the nontrivial facets of the bases polytope of M are described by the locked subsets. We

References

[1]	Oxley, J.G. (1992) Matroid Theory. Oxford University Press, Oxford.
[2]	Schrijver, A. (1986) Theory of Linear and Integer Programming. John Wiley and Sons, Chichester.
[3]	Edmonds, J. (1971) Matroids and the Greedy Algorithm. Mathematical Programming, 1, 127-136. https://doi.org/10.1007/BF01584082
[4]	Mayhew, D. (2008) Matroid Complexity and Nonsuccinct Descriptions. SIAM Journal on Discrete Mathematics, 22, 455466. https://doi.org/10.1137/050640576
[5]	Robinson, G.C. and Welsh, D.J.A. (1980) The Computational Complexity of Matroid Properties. Mathematical Proceedings of the Cambridge Philosophical Society, 87, 29-45. https://doi.org/10.1017/S0305004100056498
[6]	Chaourar, B. (2011) A Characterization of Uniform Matroids. ISRN Algebra, 2011, Article ID: 208478. https://doi.org/10.5402/2011/208478
[7]	Jensen, P.M. and Korte, B. (1982) Complexity of Matroid Property Algorithms. SIAM Journal on Computing, 11, 184-190. https://doi.org/10.1137/0211014
[8]	Giles, R. (1975) Submodular Functions, Graphs and Integer Polyhedra. PhD Thesis, University of Waterloo, Waterloo.
[9]	Pulleyblank, W.R. (1989) Polyhedral Combinatorics. In: Nemhauser, G.L., et al., Eds., Handbooks in Operations Research and Management Science, Elsevier, Amsterdam, 371-446.
[10]	Fujishige, S. (1984) A Characterization of Faces of the Base Polyhedron Associated with a Sub Modular System. Journal of the Operations Research Society of Japan, 27, 112-128. https://doi.org/10.15807/jorsj.27.112
[11]	Feichtner, E.M. and Sturmfels, B. (2005) Matroid Polytopes, Nested Sets and Bergman Fans. Portugaliae Mathematica, 62, 437-468.
[12]	Chaourar, B. (2008) On the Kth Best Basis of a Matroid. Operations Research Letters, 36, 239-242. https://doi.org/10.1016/j.orl.2007.05.007

Full-Text