ep theorem

Polynomial interior point algorithms for general LCPs

  • Marianna Eisenberg-Nagy
  • Tibor Illés
  • Tamás Terlaky
    • Categories Linear, Cone and Semidefinite Programming Tags , , ,

    Linear Complementarity Problems ($LCP$s) belong to the class of $\mathbb{NP}$-complete problems. Therefore we can not expect a polynomial time solution method for $LCP$s without requiring some special property of the matrix coefficient matrix. Our aim is to construct some interior point algorithms which, according to the duality theorem in EP form, gives a solution of … Read more

    An EP theorem for dual linear complementarity problem

  • Marianna Eisenberg-Nagy
  • Tibor Illés
  • Tamás Terlaky
    • Categories Linear, Cone and Semidefinite Programming Tags , , ,

    The linear complementarity problem (LCP) belongs to the class of NP-complete problems. Therefore we can not expect a polynomial time solution method for LCPs without requiring some special property of the matrix of the problem. We show that the dual LCP can be solved in polynomial time if the matrix is row sufficient, moreover in … Read more