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.
Similar content being viewed by others
References
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)
Fukuda, F., Namiki, M., Tamura, A.: EP theorems and linear complementarity problems. Discrete Appl. Math. 84, 107–119 (1998)
Fukuda, K., Terlaky, T.: Linear complementary and orientated matroids. J. Oper. Res. Soc. Jpn. 35, 45–61 (1992)
Cottle, R.W., Pang, J.-S., Venkateswaran, V.: Sufficient matrices and the linear complementarity problem. Linear Algebra Appl. 114/115, 231–249 (1989)
Guu, S.-M., Cottle, R.W.: On a subclass of P 0. Linear Algebra Appl. 223/224, 325–335 (1995)
Väliaho, H.: P *-matrices are just sufficient. Linear Algebra Appl. 239, 103–108 (1996)
Csizmadia, Zs., Illés, T.: New criss-cross type algorithms for linear complementarity problems with sufficient matrices. Optim. Methods Softw. 21, 247–266 (2006)
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)
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)
Illés, T., Nagy, M., Terlaky, T.: Interior point algorithms for general LCPs. J. Glob. Optim. (2008, to appear)
Author information
Authors and Affiliations
Corresponding author
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
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
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10957-008-9440-0