We present a generalization of a homogeneous self-dual linear programming (
LP) algorithm to solving the monotone complementarity problem (MCP). The al
gorithm does not need to use any "big-M" parameter or two-phase method, and
it generates either a solution converging towards feasibility and compleme
ntarity simultaneously or a certificate proving infeasibility. Moreover, if
the MCP is polynomially solvable with an interior feasible starting point,
then it can be polynomially solved without using or knowing such informati
on at all. To our knowledge, this is the first interior-point and infeasibl
e-starting algorithm for solving the MCP that possesses these desired featu
res. Preliminary computational results are presented.