A Fully Polynomial-Time Approximation Algorithm for Computing a Stationary Point of the General Linear Complementarity Problem

We apply a potential reduction algorithm to solve the general linear complementarity problem (GLCP) minimize  x T y subject to  Ax + By + Cz = q  and ( x , y , z ) 0. We show that the algorithm is a fully polynomial-time approximation scheme (FPTAS) for computing an -approximate stationary point of...

Full description

Saved in:
Bibliographic Details
Published in:Mathematics of operations research 1993-05, Vol.18 (2), p.334-345
Main Author: Ye, Yinyu
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
Approximation
Approximation algorithms
Combinatorial optimization
Exact sciences and technology
fully polynomial-time approximation scheme
Harmonic functions
Interior points
linear complementarity problem
Linear programming
Mathematical analysis
Mathematical complements
Mathematical programming
Matrices
Operational research and scientific management
Operational research. Management science
Operations research
Polynomials
potential reduction algorithm
stationary point
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We apply a potential reduction algorithm to solve the general linear complementarity problem (GLCP) minimize  x T y subject to  Ax + By + Cz = q  and ( x , y , z ) 0. We show that the algorithm is a fully polynomial-time approximation scheme (FPTAS) for computing an -approximate stationary point of the GLCP. Note that there are some GLCPs in which every stationary point is a solution ( x T y = 0). These include the LCPs with row sufficient matrices. We also show that the algorithm is a polynomial-time algorithm for a special class of GLCPs.
ISSN:0364-765X
1526-5471
DOI:10.1287/moor.18.2.334