NP-completeness of the linear complementarity problem
From MaRDI portal
Publication:1095806
DOI10.1007/BF00940344zbMath0632.90072OpenAlexW2015893008MaRDI QIDQ1095806
Publication date: 1989
Published in: Journal of Optimization Theory and Applications (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf00940344
Analysis of algorithms and problem complexity (68Q25) Linear programming (90C05) Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33)
Related Items
On the solution and complexity of a generalized linear complementarity problem, Minimum-support solutions of polyhedral concave programs*, Existence theory and \(Q\)-matrix characterization for the generalized linear complementarity problem, The Linear Complementarity Problems with a Few Variables per Constraint, The eigenvalue complementarity problem, Pivoting in linear complementarity: Two polynomial-time cases, Some LCPs solvable in strongly polynomial time with Lemke's algorithm, A fast algorithm for solving a class of the linear complementarity problem in a finite number of steps, 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, Parameterized complexity of sparse linear complementarity 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, Combinatorial characterizations of \(K\)-matrices, Distributionally robust scheduling algorithms for total flow time minimization on parallel machines using norm regularizations, EP theorems and linear complementarity problems, Absolute value equation solution via linear programming, Momentum acceleration-based matrix splitting method for solving generalized absolute value equation, A new SOR-like method for solving absolute value equations, A modified generalized SOR-like method for solving an absolute value equation, A polynomial-time algorithm for the tridiagonal and Hessenberg P-matrix linear complementarity problem, Unique end of potential line, A globally and quadratically convergent method for absolute value equations, 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 DC programming approach for solving the symmetric eigenvalue complementarity problem, Absolute value equation solution via dual complementarity, Counting unique-sink orientations, Linear complementarity as absolute value equation solution, Sign-solvable linear complementarity problems, Total dual integrality of the linear complementarity problem, Complexity of near-optimal robust versions of multilevel optimization problems, Absolute value equation solution via concave minimization, Enumeration of PLCP-orientations of the 4-cube, A generalization of the Gauss-Seidel iteration method for solving absolute value equations, A hybrid algorithm for solving the absolute value equation, A dynamic model to solve the absolute value equations, A linear complementarity based characterization of the weighted independence number and the independent domination number in graphs, Linear complementarity problems and multiple objective programming, The s-monotone index selection rule for criss-cross algorithms of linear complementarity problems, On an iterative method for solving absolute value equations, Primal-dual bilinear programming solution of the absolute value equation, On the solution of NP-hard linear complementarity problems, A class of polynomially solvable linear complementarity problems, Polynomial convergence of two higher order interior-point methods for \(P_*(\kappa)\)-LCP in a wide neighborhood of the central path, On the cone eigenvalue complementarity problem for higher-order tensors, Existence theory and \(Q\)-matrix characterization for the generalized linear complementarity problem: Revisited, A generalized Newton method for absolute value equations, The linear complementarity problem as a separable bilinear program, On the structure of linear programs with overlapping cardinality constraints, On sufficient properties of sufficient matrices, Stability of the linear complementarity problem properties under interval uncertainty, Feasible Corrector-Predictor Interior-Point Algorithm for $P_{*} (\kappa)$-Linear Complementarity Problems Based on a New Search Direction, New criss-cross type algorithms for linear complementarity problems with sufficient matrices, Knapsack feasibility as an absolute value equation solvable by successive linear programming, On Robust Solutions to Uncertain Linear Complementarity Problems and their Variants, Predictor-corrector interior-point algorithm for \(P_*(\kappa)\)-linear complementarity problems based on a new type of algebraic equivalent transformation technique, The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg, Distributionally Robust Chance Constrained Geometric Optimization, Gauss-Newton methods for the complementarity problem, Solving more linear complementarity problems with Murty's Bard-type algorithm
Cites Work
