Linear complementarity problems (LCP) are widely used for instance in industrial engineering, management science, economics, game theory and has a long history. In the late eighties, for solving several classes of LCP, mainly pivot algorithms were used. In early nineties, started by the work of Kojima and his co-authors, interior point algorithms with polynomial complexity have been developed for a wide class of LCP.
In this talk we would like to discuss the effect of the properties of matrix on the efficient solvability of LCP problems. Recently, Potra and his co-author developed an algorithm that solves any sufficient LCP in polynomial time without knowing the ? value of the matrix in advance. Following the ideas of Potra, taking into consideration the alternative theorem of LCP proved by Fukuda and Terlaky and its EP-theorem form introduced by Fukuda and his co-authors we were able to obtain some nice and general results. We showed that general linear complementarity problems can be solved in the following (EP-theorem) sense: interior point methods with a given nonnegative real parameter k, either solves (in polynomial time, depending on the size of the problem and k) the primal linear complementarity problem, or solves - in the same manner - the dual linear complementarity problem, or gives a polynomial size certificate that the matrix of the problem is not in the class of P*(k)-matrices.
Current 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996
