The Linear Complementarity Problems with a Few Variables per Constraint

References

• Aspvall B, Shiloach Y (1980) A polynomial time algorithm for solving systems of linear inequalities with two variables per inequality. SIAM J. Comput. 9:827–845.Crossref, Google Scholar
• Björklund H, Svensson O, Vorobyov S (2005) Linear complementarity algorithms for mean payoff games. Technical Report 2005-05, DIMACS: Center for Discrete Mathematics and Theoretical Computer Science, Rutgers University, Piscataway, NJ.Google Scholar
• Chandrasekaran R (1970) A special case of the complementary pivot problem. Opsearch 7:263–268.Google Scholar
• Chandrasekaran R (1984) Integer programming problems for which a simple rounding type algorithm works. Progr. Combin. Optim. 8:101–106.Crossref, Google Scholar
• Chandrasekaran R, Kabadi SN, Sridhar R (1998) Integer solution for linear complementarity problem. Math. Oper. Res. 23(2):390–402.Link, Google Scholar
• Chen X, Deng X, Teng S (2009) Settling the complexity of computing two-player Nash equilibria. J. ACM 56:1–57.Crossref, Google Scholar
• Chung SJ (1989) NP-completeness of the linear complementarity problem. J. Optim. Theory Appl. 60:393–399.Crossref, Google Scholar
• Codenotti B, Leoncini M, Resta G (2006) Efficient computation of Nash equilibria for very sparse win-lose bimatrix games. Azar Y, Erlebach T, eds. Proc. 14th Annual Eur. Sympos. Algorithms (Springer, Berlin), 232–243.Crossref, Google Scholar
• Cohen E, Megiddo N (1994) Improved algorithms for linear inequalities with two variables per inequality. SIAM J. Comput. 23: 1313–1347.Crossref, Google Scholar
• Cottle RW (1968) The principal pivoting method of quadratic programming. Mathematics of the Decision Sciences, Part 1 American Mathematical Society, Providence RI, 142–162.Google Scholar
• Cottle RW, Dantzig GB (1968) Complementary pivot theory of mathematical programming. Linear Algebra Appl. 1:103–125.Crossref, Google Scholar
• Cottle RW, Dantzig GB (1970) A generalization of the linear complementarity problem. J. Comb. Theory 8:79–90.Crossref, Google Scholar
• Cottle RW, Veinott AF (1972) Polyhedral sets having a least element. Math. Program. 3:238–249.Crossref, Google Scholar
• Cottle RW, Pang JS, Stone RE (1992) The Linear Complementarity Problem (Academic Press, Boston).Google Scholar
• Cunningham WH, Geelen JF (1998) Integral solutions of linear complementarity problems. Math. Oper. Res. 23(1):61–68.Link, Google Scholar
• Daskalakis C, Papadimitriou CH (2009) On oblivious PTAS’s for Nash equilibrium. Mitzenmacher M, ed. Proc. 41st Annual ACM Sympos. Theory Comput. (ACM, New York), 75–84.Crossref, Google Scholar
• Du Val P (1940) The unloading problem for plane curves. Amer. J. Math. 62:307–311.Crossref, Google Scholar
• Hermelin D, Huang C, Kratsch S, Wahlström M (2013) Parameterized two-player Nash equilibrium. Algorithmica 65:1–15.Crossref, Google Scholar
• Hochbaum DS, Naor J (1994) Simple and fast algorithms for linear and integer programs with two variables per inequality. SIAM J. Comput. 23:1179–1192.Crossref, Google Scholar
• Hochbaum DS, Megiddo N, Naor J, Tamir A (1993) Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality. Math. Program. 62:69–83.Crossref, Google Scholar
• Kakimura N (2008) Sign-solvable linear complementarity problems. Linear Algebra Appl. 429:606–616.Crossref, Google Scholar
• Kojima M, Megiddo N, Noma T, Yoshise A (1991) A unified approach to interior point algorithms for linear complementarity problems. Lecture Notes in Computer Science, Vol. 538 (Springer, Berlin).Crossref, Google Scholar
• Korte B, Vygen J (2012) Combinatorial Optimization: Theory and Algorithms, 5th ed. (Springer, Berlin).Crossref, Google Scholar
• Lagarias JC (1985) The computational complexity of simultaneous Diophantine approximation problems. SIAM J. Comput. 14:196–209.Crossref, Google Scholar
• Lemke CE (1965) Bimatrix equilibrium points and mathematical programming. Management Sci. 11(7):681–689.Link, Google Scholar
• Mangasarian OL (1976) Linear complementarity problems solvable by a single linear program. Math. Program. 10:263–270.Crossref, Google Scholar
• Murty KG (1997) Linear Complementarity, Linear and Nonlinear Programming, Internet edition. Accessed March 27, 2015, http://ioe.engin.umich.edu/people/fac/books/murty/linear_complementarity_webbook/lcp-complete.pdf.Google Scholar
• Ramalingam G, Song J, Joskowicz L, Miller RE (1999) Solving systems of difference constraints incrementally. Algorithmica 23: 261–275.Crossref, Google Scholar
• Schaefer TJ (1978) The complexity of satisfiability problems. Lipton RJ, Burkhard WA, Savitch WJ, Friedman EP, Aho AV, eds. Proc. 10th Annual ACM Sympos. Theory Comput. (ACM, New York), 216–226.Crossref, Google Scholar
• Schrijver A (2003) Combinatorial Optimization: Polyhedra and Efficiency (Springer, Berlin).Google Scholar
• Shostak R (1981) Deciding linear inequalities by computing loop residues. J. ACM 28:769–779.Crossref, Google Scholar
• Sumita H, Kakimura N, Makino K (2013) Sparse linear complementarity problems. Spirakis PG, Serna M, eds. Proc. 8th Internat. Conf. Algorithms and Complexity, Lecture Notes in Computer Science, Vol. 7878 (Springer, Berlin), 358–369.Crossref, Google Scholar
• Veinott AF (1989) Representation of general and polyhedral subsemilattices and sublattices of product spaces. Linear Algebra Appl. 114–115:681–704.Crossref, Google Scholar