### Abstract

Language | English |
---|---|

Pages | 1-12 |

Number of pages | 12 |

Journal | Algorithmic Operations Research |

Volume | 5 |

Issue number | 1 |

Publication status | Published - 1 Jan 2010 |

### Fingerprint

### Keywords

- linear complementarity problem
- sufficient matrix
- interior point method
- affine scaling method
- predictor-corrector algorithm

### Cite this

*Algorithmic Operations Research*,

*5*(1), 1-12.

}

*Algorithmic Operations Research*, vol. 5, no. 1, pp. 1-12.

**Polynomial interior point algorithms for general linear complementarity problems.** / Illes, Tibor; Nagy, Marianna; Terlaky, Tamás.

Research output: Contribution to journal › Article

TY - JOUR

T1 - Polynomial interior point algorithms for general linear complementarity problems

AU - Illes, Tibor

AU - Nagy, Marianna

AU - Terlaky, Tamás

PY - 2010/1/1

Y1 - 2010/1/1

N2 - Linear Complementarity Problems (LCPs) belong 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 coefficient matrix. Following our recently published ideas we generalize affine scaling and predictor-corrector interior point algorithms to solve LCPs with general matrices in EP-sense, namely, our generalized interior point algorithms either solve the problems with rational coefficient matrix in polynomial time or give a polynomial size certificate that our matrix does not belong to the set of P * (~κ) matrices, with arbitrary large, but apriori fixed, rational, positive ~κ.

AB - Linear Complementarity Problems (LCPs) belong 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 coefficient matrix. Following our recently published ideas we generalize affine scaling and predictor-corrector interior point algorithms to solve LCPs with general matrices in EP-sense, namely, our generalized interior point algorithms either solve the problems with rational coefficient matrix in polynomial time or give a polynomial size certificate that our matrix does not belong to the set of P * (~κ) matrices, with arbitrary large, but apriori fixed, rational, positive ~κ.

KW - linear complementarity problem

KW - sufficient matrix

KW - interior point method

KW - affine scaling method

KW - predictor-corrector algorithm

UR - http://journals.hil.unb.ca/index.php/AOR/article/view/11067/0

M3 - Article

VL - 5

SP - 1

EP - 12

JO - Algorithmic Operations Research

T2 - Algorithmic Operations Research

JF - Algorithmic Operations Research

SN - 1718-3235

IS - 1

ER -