Parameterized complexity of sparse linear complementarity problems

DOI10.1007/s00453-016-0229-5zbMath1372.68148OpenAlexW2533634545MaRDI QIDQ2408196

Naonori Kakimura, Kazuhisa Makino, Hanna Sumita

Publication date: 10 October 2017

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2015/5596/

zbMATH Keywords

linear complementarity problemsparsityparameterized complexity

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)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On polynomial kernels for sparse integer linear programs
• Solving linear equations parameterized by Hamming weight
• Sparse solutions of sparse linear systems: fixed-parameter tractability and an application of complex group testing
• On problems without polynomial kernels
• NP-completeness of the linear complementarity problem
• Nash and correlated equilibria: Some complexity considerations
• Parameterized two-player Nash equilibrium
• Parametrized complexity theory.
• Complementary pivot theory of mathematical programming
• On Polynomial Kernels for Integer Linear Programs: Covering, Packing and Feasibility
• On Kernels for Covering and Packing ILPs with Small Coefficients
• Settling the complexity of computing two-player Nash equilibria
• The Linear Complementarity Problems with a Few Variables per Constraint
• Simple and Fast Algorithms for Linear and Integer Programs with Two Variables Per Inequality
• Improved Algorithms For Linear Inequalities with Two Variables Per Inequality
• 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

This page was built for publication: Parameterized complexity of sparse linear complementarity problems