NP-completeness of the linear complementarity problem
From MaRDI portal
We consider the linear complementarity problem (q,M) for which the data is the integer column vector \(q\in R^ n\) and the integer square matrix M of order n. GLCP is the decision problem: Does (q,M) have a solution? We show that GLCP is NP-complete in the strong sense.
Recommendations
- On the solution and complexity of a generalized linear complementarity problem
- Existence theory and Q-matrix characterization for the generalized linear complementarity problem
- On the solution of NP-hard linear complementarity problems
- The extended linear complementarity problem
- EP theorems and linear complementarity problems
Cites work
- `` Strong NP-Completeness Results
- Computational complexity of complementary pivot methods
- Computational complexity of LCPs associated with positive definite symmetric matrices
- scientific article; zbMATH DE number 3523317 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
Cited in
(82)- Existence theory and Q-matrix characterization for the generalized linear complementarity problem: Revisited
- A generalized Newton method for absolute value equations
- Knapsack feasibility as an absolute value equation solvable by successive linear programming
- Gauss-Newton methods for the complementarity problem
- Solving more linear complementarity problems with Murty's Bard-type algorithm
- On the solution and complexity of a generalized linear complementarity problem
- EP theorems and linear complementarity problems
- Co-NP-completeness of some matrix classification problems
- Sufficient conditions for the unsolvability and solvability of the absolute value equation
- An \((m+1)\)-step iterative method of convergence order \((m+2)\) for linear complementarity problems. An \((m+1)\)-step iterative method for LCPs
- Total dual integrality of the linear complementarity problem
- A generalization of the Gauss-Seidel iteration method for solving absolute value equations
- A linear complementarity based characterization of the weighted independence number and the independent domination number in graphs
- On an iterative method for solving absolute value equations
- The linear complementarity problem as a separable bilinear program
- Existence theory and Q-matrix characterization for the generalized linear complementarity problem
- NP-completeness of a combinator optimization problem
- A polynomial-time algorithm for the tridiagonal and Hessenberg P-matrix linear complementarity problem
- Absolute value equation solution via dual complementarity
- On sufficient properties of sufficient matrices
- Stability of the linear complementarity problem properties under interval uncertainty
- Predictor-corrector interior-point algorithm for \(P_*(\kappa)\)-linear complementarity problems based on a new type of algebraic equivalent transformation technique
- A lower bound on the iterative complexity of the Harker and Pang globalization technique of the Newton-min algorithm for solving the linear complementarity problem
- A new SOR-like method for solving absolute value equations
- Unique end of potential line
- Complexity of near-optimal robust versions of multilevel optimization problems
- On the structure of linear programs with overlapping cardinality constraints
- Pivoting in linear complementarity: Two polynomial-time cases
- Parameterized complexity of sparse linear complementarity problems
- Counting unique-sink orientations
- Linear complementarity as absolute value equation solution
- Absolute value equation solution via concave minimization
- A class of polynomially solvable linear complementarity problems
- The eigenvalue complementarity problem
- A fast algorithm for solving a class of the linear complementarity problem in a finite number of steps
- Distributionally robust scheduling algorithms for total flow time minimization on parallel machines using norm regularizations
- On robust solutions to uncertain linear complementarity problems and their variants
- Some LCPs solvable in strongly polynomial time with Lemke's algorithm
- The Linear Complementarity Problems with a Few Variables per Constraint
- Absolute value equation solution via linear programming
- Minimum-support solutions of polyhedral concave programs*
- A DC programming approach for solving the symmetric eigenvalue complementarity problem
- Enumeration of PLCP-orientations of the 4-cube
- Feasible corrector-predictor interior-point algorithm for \(P_* (\kappa)\)-linear complementarity problems based on a new search direction
- A hybrid algorithm for solving the absolute value equation
- LaserTank is NP-Complete
- The s-monotone index selection rule for criss-cross algorithms of linear complementarity problems
- The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
- New criss-cross type algorithms for linear complementarity problems with sufficient matrices
- Distributionally Robust Chance Constrained Geometric Optimization
- On the cone eigenvalue complementarity problem for higher-order tensors
- Momentum acceleration-based matrix splitting method for solving generalized absolute value equation
- Combinatorial characterizations of \(K\)-matrices
- A modified generalized SOR-like method for solving an absolute value equation
- Interior-point algorithm for symmetric cone horizontal linear complementarity problems based on a new class of algebraically equivalent transformations
- Tropical Complementarity Problems and Nash Equilibria
- A globally and quadratically convergent method for absolute value equations
- Large-step predictor-corrector interior point method for sufficient linear complementarity problems based on the algebraic equivalent transformation
- A dimension expanded Newton-type method for absolute value equations
- Unified approach of interior-point algorithms for P_* ()-LCPs using a new class of algebraically equivalent transformations
- New predictor-corrector algorithm for symmetric cone horizontal linear complementarity problems
- A new Ai-Zhang type interior point algorithm for sufficient linear complementarity problems
- The generalized fixed point iteration method for AVE
- Newton-based alternate matrix multi-splitting method for generalized absolute value equation
- A dynamic model to solve the absolute value equations
- Computational complexity of the -Ham-Sandwich problem
- A feasible interior-point method with full-Newton step for P_* ( )-weighted linear complementarity problem via the algebraically equivalent transformation
- Polyhedral Newton-min algorithms for complementarity problems
- Linear complementarity problems and multiple objective programming
- On solving a larger subclass of linear complementarity problems by Lemke's method
- Univariate representations of solutions to generic polynomial complementarity problems
- Primal-dual bilinear programming solution of the absolute value equation
- Multiple faces of optimization. A tribute to Tamás Terlaky on his 70th birthday
- On the solution of NP-hard linear complementarity problems
- New predictor-corrector interior-point algorithm with AET function having inflection points
- Two efficient iteration methods for solving the absolute value equations
- Polynomial convergence of two higher order interior-point methods for \(P_*(\kappa)\)-LCP in a wide neighborhood of the central path
- An open Newton method for piecewise smooth systems
- On covering euclidean space with Q-arrangements of cones
- A novel corrector–predictor interior-point algorithm for P * (κ)-weighted linear complementarity problems based on an AET function
- NP-completeness of the Hamming salesman problem
- Sign-solvable linear complementarity problems
This page was built for publication: NP-completeness of the linear complementarity problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1095806)