Manchester Metropolitan University's Research Repository

    Pivoting in Linear Complementarity: Two Polynomial-Time Cases

    Foniok, J, Fukuda, K, Gaertner, B and Luethi, H-J (2009) Pivoting in Linear Complementarity: Two Polynomial-Time Cases. Discrete & Computational Geometry, 42. ISSN 0179-5376


    Download (254kB) | Preview


    We study the behavior of simple principal pivoting methods for the P-matrix linear complementarity problem (P-LCP). We solve an open problem of Morris by showing that Murty’s least-index pivot rule (under any fixed index order) leads to a quadratic number of iterations on Morris’s highly cyclic P-LCP examples. We then show that on K-matrix LCP instances, all pivot rules require only a linear number of iterations. As the main tool, we employ unique-sink orientations of cubes, a useful combinatorial abstraction of the P-LCP.

    Impact and Reach


    Activity Overview
    6 month trend
    6 month trend

    Additional statistics for this dataset are available via IRStats2.


    Actions (login required)

    View Item View Item