Digraph Models of Bard-Type Algorithms for the Linear Complementarity Problem

DOI10.1287/MOOR.3.4.322MaRDI QIDQ4180165zbMATH OpenOpenAlexFDO

Authors Alan Stickney, Layne T. Watson

Publication date 1978

Published in Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1287/moor.3.4.322

zbMATH Keywords

CyclingP-MatricesDigraph ModelsLinear Complementarity Problem

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33) Linear inequalities of matrices (15A39)

Cited in

(19)

• Enumeration of PLCP-orientations of the 4-cube
• Exponential lower bounds for history-based simplex pivot rules on abstract cubes
• Unique sink orientations of grids
• A Simple P-Matrix Linear Complementarity Problem for Discounted Games
• Solving more linear complementarity problems with Murty's Bard-type algorithm
• On the existence of Hamiltonian paths for history based pivot rules on acyclic unique sink orientations of hypercubes
• A variable dimension algorithm for the linear complementarity problem
• Computational complexity of LCPs associated with positive definite symmetric matrices
• Pivoting in linear complementarity: Two polynomial-time cases
• Combinatorial characterizations of \(K\)-matrices
• Unique end of potential line
• A Mihalisin-Klee theorem for fans
• Observations on a class of nasty linear complementarity problems
• A complexity analysis of policy iteration through combinatorial matrices arising from unique sink orientations
• A polynomial-time algorithm for the tridiagonal and Hessenberg P-matrix linear complementarity problem
• Realizability makes a difference: a complexity gap for sink-finding in USOs
• On the Holt-Klee property for oriented matroid programming
• An exponential lower bound for Cunningham's rule
• Counting unique-sink orientations

This page was built for publication: Digraph Models of Bard-Type Algorithms for the Linear Complementarity Problem

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