Fulltext

Pivoting in Linear Complementarity: TwoPolynomial-Time Cases

Foniok, Jan ; Fukuda, Komei ; Gärtner, Bernd ; Lüthi, Hans-Jakob

In: Discrete & Computational Geometry, 2009, vol. 42, no. 2, p. 187-205

Zum persönliche Liste hinzufügen
    Titel
    • Pivoting in Linear Complementarity: TwoPolynomial-Time Cases
    Autor
    • Foniok, Jan. Institute for Operations Research, ETH Zurich, 8092, Zurich, Switzerland
    • Fukuda, Komei. Institute for Operations Research, ETH Zurich, 8092, Zurich, Switzerland
    • Gärtner, Bernd. Institute of Theoretical Computer Science, ETH Zurich, 8092, Zurich, Switzerland
    • Lüthi, Hans-Jakob. Institute for Operations Research, ETH Zurich, 8092, Zurich, Switzerland
    Dokumententyp
    • Postprint
    Sprache
    • Englisch
    Veröffentlicht in
    • Discrete & Computational Geometry, 2009, vol. 42, no. 2, p. 187-205. Springer-Verlag
    Andere elektronische Ausgabe
    OAI-PMH-ID
    • oai:doc.rero.ch:322183
    Summary
    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