LINEAR COMPLEMENTARITY AND ORIENTED MATROIDS

スポンサーリンク

概要

• 論文の詳細を見る

• A combinatorial abstraction of the linear complementarity theory in the setting of oriented matroids was first considered by M.J. Todd. In this paper, we take a fresh look at this abstraction, and attempt to give a simple treatment of the combinatorial theory of linear complementarity. We obtain new theorems, proofs and algorithms in oriented matroids whose specializations to the linear case are also new. For this, the notion of sufficiency of square matrices, introduced by Cottle, Pang and Venkateswaran, is extended to oriented matroids. Then, we prove a sort of duality theorem for oriented matroids, which roughly states: exactly one of the primal and the dual system has a complementary solution if the associated oriented matroid satisfies "weak" sufficiency. We give two different proofs for this theorem, an elementary inductive proof and an algorithmic proof using the criss-cross method which solves one of the primal or dual problem by using surprisingly simple pivot rules (without any perturbation of the original problem).

著者

• Fukuda K

  Graduate School Of Systems Management University Of Tsukuba

• Fukuda Komei

  Graduate School Of Systems Management University Of Tsukuba

• Terlaky Tamas

  Faculty of Technical Mathematics and Informatics, Delft University of Technology

関連論文

• LINEAR COMPLEMENTARITY AND ORIENTED MATROIDS
• McMullen's conditions and some lower bounds for general convex polytopes
• Wagner's theorem and combinatorial enumeration of 3-polytopes(Computational Geometry and Discrete Geometry)
• Wagner's theorem and combinatorial enumeration of 3-polytopes

スポンサーリンク