Enumeration of PLCP-orientations of the 4-cube
From MaRDI portal
(Redirected from Publication:491752)
Exact enumeration problems, generating functions (05A15) Combinatorial aspects of matroids and geometric lattices (05B35) Directed graphs (digraphs), tournaments (05C20) Linear inequalities of matrices (15A39) Linear programming (90C05) Quadratic programming (90C20) Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33)
Abstract: The linear complementarity problem (LCP) provides a unified approach to many problems such as linear programs, convex quadratic programs, and bimatrix games. The general LCP is known to be NP-hard, but there are some promising results that suggest the possibility that the LCP with a P-matrix (PLCP) may be polynomial-time solvable. However, no polynomial-time algorithm for the PLCP has been found yet and the computational complexity of the PLCP remains open. Simple principal pivoting (SPP) algorithms, also known as Bard-type algorithms, are candidates for polynomial-time algorithms for the PLCP. In 1978, Stickney and Watson interpreted SPP algorithms as a family of algorithms that seek the sink of unique-sink orientations of -cubes. They performed the enumeration of the arising orientations of the -cube, hereafter called PLCP-orientations. In this paper, we present the enumeration of PLCP-orientations of the -cube.The enumeration is done via construction of oriented matroids generalizing P-matrices and realizability classification of oriented matroids.Some insights obtained in the computational experiments are presented as well.
Recommendations
- Randomized pivot algorithms for \(P\)-matrix linear complementarity problems
- Pivoting in linear complementarity: Two polynomial-time cases
- EP theorems and linear complementarity problems
- NP-completeness of the linear complementarity problem
- Two counterexamples on the polynomial solvability of the linear complementarity problem
Cites work
- A Partition Theorem for Euclidean n-Space
- A polynomial-time algorithm for a class of linear complementarity problems
- A Probelm in Linear Inequalities
- A unified approach to interior point algorithms for linear complementarity problems: A summary
- Bimatrix Equilibrium Points and Mathematical Programming
- Combinatorial characterizations of \(K\)-matrices
- Complementarity in Oriented Matroids
- Complementary pivot theory of mathematical programming
- Complete enumeration of small realizable oriented matroids
- Counting unique-sink orientations
- Digraph Models of Bard-Type Algorithms for the Linear Complementarity Problem
- Equilibrium Points of Bimatrix Games
- Generation of oriented matroids --- a graph theoretical approach
- Higher Bruhat orders and cyclic hyperplane arrangements
- scientific article; zbMATH DE number 3159112 (Why is no real title available?)
- scientific article; zbMATH DE number 4092241 (Why is no real title available?)
- scientific article; zbMATH DE number 53115 (Why is no real title available?)
- scientific article; zbMATH DE number 3538668 (Why is no real title available?)
- scientific article; zbMATH DE number 3212891 (Why is no real title available?)
- scientific article; zbMATH DE number 2209726 (Why is no real title available?)
- LINEAR COMPLEMENTARITY AND ORIENTED MATROIDS
- Linear complementarity problems solvable by a polynomially bounded pivoting algorithm
- Linear complementarity problems solvable by A single linear program
- Linear programming and unique sink orientations
- LP-orientations of cubes and crosspolytopes
- NP-completeness of the linear complementarity problem
- On the generation of oriented matroids
- On the number of solutions to the complementarity problem and spanning properties of complementary cones
- Oriented Matroids
- Pivoting in linear complementarity: Two polynomial-time cases
- Randomized pivot algorithms for \(P\)-matrix linear complementarity problems
- Some generalizations of the criss-cross method for the linear complementarity problem of oriented matroids
- Unique sink orientations of grids
Cited in
(5)- On the Holt-Klee property for oriented matroid programming
- A Mihalisin-Klee theorem for fans
- Realizability makes a difference: a complexity gap for sink-finding in USOs
- Realizability in Matoušek unique sink orientations: characterization and complexity gap
- On degeneracy in the P-matroid oriented matroid complementarity problem
This page was built for publication: Enumeration of PLCP-orientations of the 4-cube
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q491752)
