Skip to main content
SpringerLink
Log in

EP Theorem for Dual Linear Complementarity Problems

  • Published:
Journal of Optimization Theory and Applications Aims and scope Submit manuscript

Abstract

The linear complementarity problem (LCP) belongs to the class of \(\mathbb{NP}\) -hard problems. Therefore, we cannot 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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Kojima, M., Megiddo, N., Noma, T., Yoshise, A.: A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems. Lecture Notes in Computer Science, vol. 538. Springer, Berlin (1991)

    Google Scholar 

  2. Fukuda, F., Namiki, M., Tamura, A.: EP theorems and linear complementarity problems. Discrete Appl. Math. 84, 107–119 (1998)

    Article  MathSciNet  Google Scholar 

  3. Fukuda, K., Terlaky, T.: Linear complementary and orientated matroids. J. Oper. Res. Soc. Jpn. 35, 45–61 (1992)

    MathSciNet  Google Scholar 

  4. Cottle, R.W., Pang, J.-S., Venkateswaran, V.: Sufficient matrices and the linear complementarity problem. Linear Algebra Appl. 114/115, 231–249 (1989)

    Article  MathSciNet  Google Scholar 

  5. Guu, S.-M., Cottle, R.W.: On a subclass of P 0. Linear Algebra Appl. 223/224, 325–335 (1995)

    Article  MathSciNet  Google Scholar 

  6. Väliaho, H.: P *-matrices are just sufficient. Linear Algebra Appl. 239, 103–108 (1996)

    MathSciNet  Google Scholar 

  7. Csizmadia, Zs., Illés, T.: New criss-cross type algorithms for linear complementarity problems with sufficient matrices. Optim. Methods Softw. 21, 247–266 (2006)

    Article  MathSciNet  Google Scholar 

  8. Cameron, K., Edmonds, J.: Existentially polytime theorems. In: Polyhedral Combinatorics. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 1, pp. 83–100. American Mathematical Society, Providence (1990)

    Google Scholar 

  9. Roos, C., Terlaky, T., Vial, J.-Ph.: Theory and Algorithms for Linear Optimization, An Interior Point Approach. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley, New York (1997). 2nd edn. Interior Point Methods for Linear Optimization. Springer, New York (2006)

    Google Scholar 

  10. Illés, T., Nagy, M., Terlaky, T.: Interior point algorithms for general LCPs. J. Glob. Optim. (2008, to appear)

Download references

Author information

Authors and Affiliations

  1. Department of Management Science, Strathclyde University, Glasgow, UK

    T. Illés

  2. Department of Operation Research, Eötvös Lorànd University of Science, Budapest, Hungary

    M. Nagy

  3. Department of Computing and Software, School of Computational Engineering and Science, McMaster University, Hamilton, Ontario, Canada

    T. Terlaky

Authors
  1. T. Illés
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. M. Nagy
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. T. Terlaky
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to T. Illés.

Additional information

Communicated by F.A. Potra.

The research of Tibor Illés and Marianna Nagy has been supported by the Hungarian National Research Fund OTKA T 049789 and by the Hungarian Science and Technology Foundation TÉT SLO-4/2005.

Tamàs Terlaky has been supported by an NSERC Discovery grant, MITACS and the Canada Research Chair program.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Illés, T., Nagy, M. & Terlaky, T. EP Theorem for Dual Linear Complementarity Problems. J Optim Theory Appl 140, 233–238 (2009). https://doi.org/10.1007/s10957-008-9440-0

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10957-008-9440-0

Keywords

Search

Navigation