Abstract
In this paper, we study the sparse linear complementarity problem, denoted by k-LCP: the coefficient matrix has at most k nonzero entries per row. It is known that 1-LCP is solvable in linear time, while 3-LCP is strongly NP-hard. We show that 2-LCP is strongly NP-hard, while it can be solved in O(n 3 logn) time if it is sign-balanced, i.e., each row has at most one positive and one negative entries, where n is the number of constraints. Our second result matches with the currently best known complexity bound for the corresponding sparse linear feasibility problem. In addition, we show that an integer variant of sign-balanced 2-LCP is weakly NP-hard and pseudo-polynomially solvable, and the generalized 1-LCP is strongly NP-hard.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aspvall, B., Shiloach, Y.: A polynomial time algorithm for solving systems of linear inequalities with two variables per inequality. SIAM Journal on Computing 9, 827–845 (1980)
Björklund, H., Svensson, O., Vorobyov, S.: Linear complementarity algorithms for mean payoff games. Technical Report 2005-05, DIMACS: Center for Discrete Mathematics and Theoretical Computer Science (2005)
Chandrasekaran, R.: A special case of the complementary pivot problem. Opsearch 7, 263–268 (1970)
Chandrasekaran, R.: Integer programming problems for which a simple rounding type algorithm works. Combinatorial Optimization 8, 101–106 (1984)
Chandrasekaran, R., Kabadi, S.N., Sridhar, R.: Integer solution for linear complementarity problem. Mathematics of Operations Research 23, 390–402 (1998)
Chen, X., Deng, X., Teng, S.-H.: Sparse games are hard. In: Spirakis, P.G., Mavronicolas, M., Kontogiannis, S.C. (eds.) WINE 2006. LNCS, vol. 4286, pp. 262–273. Springer, Heidelberg (2006)
Chung, S.J.: NP-completeness of the linear complementarity problem. Journal of Optimization Theory and Applications 60, 393–399 (1989)
Codenotti, B., Leoncini, M., Resta, G.: Efficient computation of nash equilibria for very sparse win-lose bimatrix games. In: Azar, Y., Erlebach, T. (eds.) ESA 2006. LNCS, vol. 4168, pp. 232–243. Springer, Heidelberg (2006)
Cohen, E., Megiddo, N.: Improved algorithms for linear inequalities with two variables per inequality. SIAM Journal on Computing 23, 1313–1347 (1994)
Cottle, R.W.: The principal pivoting method of quadratic programming. In: Dantzig, G.B., Veinott, A.F. (eds.) Mathematics of Decision Sciences, Part 1, pp. 142–162. American Mathematical Society, Providence R. I. (1968)
Cottle, R.W., Dantzig, G.B.: Complementary pivot theory of mathematical programming. Linear Algebra and Its Applications 1, 103–125 (1968)
Cottle, R.W., Dantzig, G.B.: A generalization of the linear complementarity problem. Journal on Combinatorial Theory 8, 79–90 (1970)
Cottle, R.W., Pang, J.S., Stone, R.E.: The Linear Complementarity Problem. Academic Press, Boston (1992)
Cottle, R.W., Veinott, A.F.: Polyhedral sets having a least element. Mathematical Programming 3, 238–249 (1972)
Cunningham, W.H., Geelen, J.F.: Integral solutions of linear complementarity problems. Mathematics of Operations Research 23, 61–68 (1998)
Daskalakis, C., Papadimitriou, C.H.: On oblivious PTAS’s for Nash equilibrium. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing, pp. 75–84 (2009)
Du Val, P.: The unloading problem for plane curves. American Journal of Mathematics 62, 307–311 (1940)
Hermelin, D., Huang, C., Kratsch, S., Wahlström, M.: Parameterized two-player Nash equilibrium. Algorithmica, 1–15 (2012)
Hochbaum, D.S., Megiddo, N., Naor, J., Tamir, A.: Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality. Mathematical Programming 62, 69–83 (1993)
Hochbaum, D.S., Naor, J.: Simple and fast algorithms for linear and integer programs with two variables per inequality. SIAM Journal on Computing 23, 1179–1192 (1994)
Kakimura, N.: Sign-solvable linear complementarity problems. Linear Algebra and Its Applications 429, 606–616 (2008)
Kojima, M., Megiddo, N., Noma, T., Yoshise, A.: A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems. LNCS, vol. 538. Springer, Heidelberg (1991)
Lagarias, J.C.: The computational complexity of simultaneous Diophantine approximation problems. SIAM Journal on Computing 14, 196–209 (1985)
Lemke, C.E.: Bimatrix equilibrium points and mathematical programming. Management Science 11, 681–689 (1965)
Mangasarian, O.L.: Linear complementarity problems solvable by a single linear program. Mathematical Programming 10, 263–270 (1976)
Murty, K.G.: Linear Complementarity, Linear and Nonlinear Programming. Internet Edition (1997)
Samelson, H., Thrall, R.M., Wesler, O.: A partition theorem for Euclidean n-space. Proceedings of the American Mathematical Society 9, 805–807 (1958)
Schaefer, T.J.: The complexity of satisfiability problems. In: Proceedings of the 10th Annual ACM Symposium on Theory of Computing, pp. 216–226 (1978)
Shostak, R.: Deciding linear inequalities by computing loop residues. Journal of the ACM 28, 769–779 (1981)
Sumita, H., Kakimura, N., Makino, K.: Sparse linear complementarity problems. METR 2013-02, Department of Mathematical Informatics, University of Tokyo (2013)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Sumita, H., Kakimura, N., Makino, K. (2013). Sparse Linear Complementarity Problems. In: Spirakis, P.G., Serna, M. (eds) Algorithms and Complexity. CIAC 2013. Lecture Notes in Computer Science, vol 7878. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-38233-8_30
Download citation
DOI: https://doi.org/10.1007/978-3-642-38233-8_30
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-38232-1
Online ISBN: 978-3-642-38233-8
eBook Packages: Computer ScienceComputer Science (R0)