Parameterized complexity of sparse linear complementarity problems
From MaRDI portal
Publication:2408196
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/
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
