Parameterized complexity of sparse linear complementarity problems

DOI10.1007/S00453-016-0229-5zbMATH Open1372.68148OpenAlexW2533634545MaRDI QIDQ2408196FDOQ2408196

Authors Hanna Sumita, Naonori Kakimura, Kazuhisa Makino 

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

sparsitylinear complementarity problemparameterized 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)

Recommendations

• Parameterized complexity of sparse linear complementarity problems
• Sparse Linear Complementarity Problems
• Sparse solutions of linear complementarity problems
• Sparse parameterized problems
• Approximation Bounds for Sparse Programs
• On the complexity of sparse elimination
• On the parametric linear complementarity problem
• Approximability of Sparse Integer Programs
• Approximability of sparse integer programs
• PRACTICAL POLYNOMIAL TIME ALGORITHMS FOR LINEAR COMPLEMENTARITY PROBLEMS

Cites Work

• scientific article; zbMATH DE number 53115 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 3312380 (Why is no real title available?)
• Bimatrix Equilibrium Points and Mathematical Programming
• Complementary pivot theory of mathematical programming
• Efficient Computation of Nash Equilibria for Very Sparse Win-Lose Bimatrix Games
• Improved Algorithms For Linear Inequalities with Two Variables Per Inequality
• NP-completeness of the linear complementarity problem
• Nash and correlated equilibria: Some complexity considerations
• On Polynomial Kernels for Integer Linear Programs: Covering, Packing and Feasibility
• On kernels for covering and packing ILPs with small coefficients
• On oblivious PTAS's for nash equilibrium
• On polynomial kernels for sparse integer linear programs
• On problems without polynomial kernels
• Parametrized complexity theory.
• Settling the complexity of computing two-player Nash equilibria
• Simple and Fast Algorithms for Linear and Integer Programs with Two Variables Per Inequality
• Solving linear equations parameterized by Hamming weight
• Sparse solutions of sparse linear systems: fixed-parameter tractability and an application of complex group testing
• The Linear Complementarity Problems with a Few Variables per Constraint

Cited In (3)

• Sparse Linear Complementarity Problems
• Sparse semidefinite programs with guaranteed near-linear time complexity via dualized clique tree conversion
• Parameterized complexity of sparse linear complementarity problems

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

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