The Linear Complementarity Problems with a Few Variables per Constraint

DOI10.1287/MOOR.2014.0708MaRDI QIDQ3465945zbMATH OpenOpenAlexFDO

Authors Hanna Sumita, Naonori Kakimura, Kazuhisa Makino

Publication date 29 January 2016

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

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

zbMATH Keywords

linear complementarity problemNP-hardnesscombinatorial algorithmpolynomial solvabilitytwo-variable constraints

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33)

Recommendations

• On linear problems with complementarity constraints
• On linear programs with linear complementarity constraints
• Linear complementarity problems solvable as linear programs
• On the Solution Sets of Linear Complementarity Problems
• Linear complementarity problems solvable by integer programming
• Linear complementarity problems and multiple objective programming
• Solving the linear complementarity problem through concave programming
• Linear complementarity problems with an invariant number of solutions
• Solution of linear complementarity problems using minimization with simple bounds
• Linear complementarity problems solvable by A single linear program

Cites work

• scientific article; zbMATH DE number 3880440 (Why is no real title available?)
• A Polynomial Time Algorithm for Solving Systems of Linear Inequalities with Two Variables Per Inequality
• A generalization of the linear complementarity problem
• A unified approach to interior point algorithms for linear complementarity problems: A summary
• Bimatrix Equilibrium Points and Mathematical Programming
• Combinatorial optimization. Theory and algorithms.
• Complementary pivot theory of mathematical programming
• Deciding Linear Inequalities by Computing Loop Residues
• Efficient Computation of Nash Equilibria for Very Sparse Win-Lose Bimatrix Games
• Improved Algorithms For Linear Inequalities with Two Variables Per Inequality
• Integer solution for linear complementarity problem
• Integral solutions of linear complementarity problems
• Linear complementarity problems solvable by A single linear program
• NP-completeness of the linear complementarity problem
• On oblivious PTAS's for nash equilibrium
• Polyhedral sets having a least element
• Settling the complexity of computing two-player Nash equilibria
• Sign-solvable linear complementarity problems
• Simple and Fast Algorithms for Linear and Integer Programs with Two Variables Per Inequality
• Solving systems of difference constraints incrementally
• Sparse Linear Complementarity Problems
• The Computational Complexity of Simultaneous Diophantine Approximation Problems
• The Unloading Problem for Plane Curves
• Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality

Cited in

(6)

• Sparse solutions of linear complementarity problems
• Sign-solvable linear complementarity problems
• Parameterized complexity of sparse linear complementarity problems
• Piecewise linear valued constraint satisfaction problems with fixed number of variables
• Parameterized complexity of sparse linear complementarity problems
• Solving linear optimization problems with max-star composition equation constraints

This page was built for publication: The Linear Complementarity Problems with a Few Variables per Constraint

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