### Abstract

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 this case all feasible solutions are complementary. Furthermore we present an existentially polytime (EP) theorem for the dual LCP with arbitrary matrix.

Original language | English |
---|---|

Title of host publication | SOR'07 |

Subtitle of host publication | The 9th International Symposium on Operational Research in Slovenia Nova Gorica, SLOVENIA, September 26 - 28, 2007 |

Editors | ZadnikStirn L, Drobne S |

Place of Publication | Ljubljana |

Pages | 123-127 |

Number of pages | 5 |

Publication status | Published - 28 Sep 2007 |

### Keywords

- linear complementarity problem
- row sufficient matrix
- EP theorem

## Fingerprint Dive into the research topics of 'An EP theorem for DLCP and interior point methods'. Together they form a unique fingerprint.

## Cite this

Illés, T., Nagy, M., & Terlaky, T. (2007). An EP theorem for DLCP and interior point methods. In Z. L, & D. S (Eds.),

*SOR'07: The 9th International Symposium on Operational Research in Slovenia Nova Gorica, SLOVENIA, September 26 - 28, 2007*(pp. 123-127).