The Linear Complementarity Problems with a Few Variables per Constraint

DOI10.1287/moor.2014.0708zbMath1329.90147OpenAlexW2142656615MaRDI QIDQ3465945

Hanna Sumita, Kazuhisa Makino, Naonori Kakimura

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)

Related Items (1)

Parameterized complexity of sparse linear complementarity problems

Cites Work

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

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