Yy. Ye, A FULLY POLYNOMIAL-TIME APPROXIMATION ALGORITHM FOR COMPUTING A STATIONARY POINT OF THE GENERAL LINEAR COMPLEMENTARITY-PROBLEM, Mathematics of operations research, 18(2), 1993, pp. 334-345
Citations number
23
Categorie Soggetti
Operatione Research & Management Science",Mathematics,"Operatione Research & Management Science",Mathematics
We apply a potential reduction algorithm to solve the general linear c
omplementarity problem (GLCP) minimize x(T)y subject to Ax + By + Cz =
q and (x, y, z) greater-than-or-equal-to 0. We show that the algorith
m is a fully polynomial-time approximation scheme (FPTAS) for computin
g an epsilon-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.