{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T15:59:18Z","timestamp":1725465558722},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642382321"},{"type":"electronic","value":"9783642382338"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-38233-8_30","type":"book-chapter","created":{"date-parts":[[2013,5,15]],"date-time":"2013-05-15T12:57:16Z","timestamp":1368622636000},"page":"358-369","source":"Crossref","is-referenced-by-count":2,"title":["Sparse Linear Complementarity Problems"],"prefix":"10.1007","author":[{"given":"Hanna","family":"Sumita","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Naonori","family":"Kakimura","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kazuhisa","family":"Makino","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"30_CR1","doi-asserted-by":"publisher","first-page":"827","DOI":"10.1137\/0209063","volume":"9","author":"B. Aspvall","year":"1980","unstructured":"Aspvall, B., Shiloach, Y.: A polynomial time algorithm for solving systems of linear inequalities with two variables per inequality. SIAM Journal on Computing\u00a09, 827\u2013845 (1980)","journal-title":"SIAM Journal on Computing"},{"key":"30_CR2","unstructured":"Bj\u00f6rklund, 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)"},{"key":"30_CR3","first-page":"263","volume":"7","author":"R. Chandrasekaran","year":"1970","unstructured":"Chandrasekaran, R.: A special case of the complementary pivot problem. Opsearch\u00a07, 263\u2013268 (1970)","journal-title":"Opsearch"},{"key":"30_CR4","first-page":"101","volume":"8","author":"R. Chandrasekaran","year":"1984","unstructured":"Chandrasekaran, R.: Integer programming problems for which a simple rounding type algorithm works. Combinatorial Optimization\u00a08, 101\u2013106 (1984)","journal-title":"Combinatorial Optimization"},{"key":"30_CR5","doi-asserted-by":"publisher","first-page":"390","DOI":"10.1287\/moor.23.2.390","volume":"23","author":"R. Chandrasekaran","year":"1998","unstructured":"Chandrasekaran, R., Kabadi, S.N., Sridhar, R.: Integer solution for linear complementarity problem. Mathematics of Operations Research\u00a023, 390\u2013402 (1998)","journal-title":"Mathematics of Operations Research"},{"key":"30_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1007\/11944874_24","volume-title":"Internet and Network Economics","author":"X. Chen","year":"2006","unstructured":"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.\u00a04286, pp. 262\u2013273. Springer, Heidelberg (2006)"},{"key":"30_CR7","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1007\/BF00940344","volume":"60","author":"S.J. Chung","year":"1989","unstructured":"Chung, S.J.: NP-completeness of the linear complementarity problem. Journal of Optimization Theory and Applications\u00a060, 393\u2013399 (1989)","journal-title":"Journal of Optimization Theory and Applications"},{"key":"30_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1007\/11841036_23","volume-title":"Algorithms \u2013 ESA 2006","author":"B. Codenotti","year":"2006","unstructured":"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.\u00a04168, pp. 232\u2013243. Springer, Heidelberg (2006)"},{"key":"30_CR9","doi-asserted-by":"publisher","first-page":"1313","DOI":"10.1137\/S0097539791256325","volume":"23","author":"E. Cohen","year":"1994","unstructured":"Cohen, E., Megiddo, N.: Improved algorithms for linear inequalities with two variables per inequality. SIAM Journal on Computing\u00a023, 1313\u20131347 (1994)","journal-title":"SIAM Journal on Computing"},{"key":"30_CR10","unstructured":"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\u2013162. American Mathematical Society, Providence R. I. (1968)"},{"key":"30_CR11","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1016\/0024-3795(68)90052-9","volume":"1","author":"R.W. Cottle","year":"1968","unstructured":"Cottle, R.W., Dantzig, G.B.: Complementary pivot theory of mathematical programming. Linear Algebra and Its Applications\u00a01, 103\u2013125 (1968)","journal-title":"Linear Algebra and Its Applications"},{"key":"30_CR12","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/S0021-9800(70)80010-2","volume":"8","author":"R.W. Cottle","year":"1970","unstructured":"Cottle, R.W., Dantzig, G.B.: A generalization of the linear complementarity problem. Journal on Combinatorial Theory\u00a08, 79\u201390 (1970)","journal-title":"Journal on Combinatorial Theory"},{"key":"30_CR13","volume-title":"The Linear Complementarity Problem","author":"R.W. Cottle","year":"1992","unstructured":"Cottle, R.W., Pang, J.S., Stone, R.E.: The Linear Complementarity Problem. Academic Press, Boston (1992)"},{"key":"30_CR14","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1007\/BF01584992","volume":"3","author":"R.W. Cottle","year":"1972","unstructured":"Cottle, R.W., Veinott, A.F.: Polyhedral sets having a least element. Mathematical Programming\u00a03, 238\u2013249 (1972)","journal-title":"Mathematical Programming"},{"key":"30_CR15","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1287\/moor.23.1.61","volume":"23","author":"W.H. Cunningham","year":"1998","unstructured":"Cunningham, W.H., Geelen, J.F.: Integral solutions of linear complementarity problems. Mathematics of Operations Research\u00a023, 61\u201368 (1998)","journal-title":"Mathematics of Operations Research"},{"key":"30_CR16","doi-asserted-by":"crossref","unstructured":"Daskalakis, C., Papadimitriou, C.H.: On oblivious PTAS\u2019s for Nash equilibrium. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing, pp. 75\u201384 (2009)","DOI":"10.1145\/1536414.1536427"},{"key":"30_CR17","doi-asserted-by":"publisher","first-page":"307","DOI":"10.2307\/2371454","volume":"62","author":"P. Val Du","year":"1940","unstructured":"Du Val, P.: The unloading problem for plane curves. American Journal of Mathematics\u00a062, 307\u2013311 (1940)","journal-title":"American Journal of Mathematics"},{"key":"30_CR18","doi-asserted-by":"crossref","unstructured":"Hermelin, D., Huang, C., Kratsch, S., Wahlstr\u00f6m, M.: Parameterized two-player Nash equilibrium. Algorithmica, 1\u201315 (2012)","DOI":"10.1007\/s00453-011-9609-z"},{"key":"30_CR19","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1007\/BF01585160","volume":"62","author":"D.S. Hochbaum","year":"1993","unstructured":"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\u00a062, 69\u201383 (1993)","journal-title":"Mathematical Programming"},{"key":"30_CR20","doi-asserted-by":"publisher","first-page":"1179","DOI":"10.1137\/S0097539793251876","volume":"23","author":"D.S. Hochbaum","year":"1994","unstructured":"Hochbaum, D.S., Naor, J.: Simple and fast algorithms for linear and integer programs with two variables per inequality. SIAM Journal on Computing\u00a023, 1179\u20131192 (1994)","journal-title":"SIAM Journal on Computing"},{"key":"30_CR21","doi-asserted-by":"publisher","first-page":"606","DOI":"10.1016\/j.laa.2008.03.022","volume":"429","author":"N. Kakimura","year":"2008","unstructured":"Kakimura, N.: Sign-solvable linear complementarity problems. Linear Algebra and Its Applications\u00a0429, 606\u2013616 (2008)","journal-title":"Linear Algebra and Its Applications"},{"key":"30_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-54509-3","volume-title":"A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems","author":"M. Kojima","year":"1991","unstructured":"Kojima, M., Megiddo, N., Noma, T., Yoshise, A.: A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems. LNCS, vol.\u00a0538. Springer, Heidelberg (1991)"},{"key":"30_CR23","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1137\/0214016","volume":"14","author":"J.C. Lagarias","year":"1985","unstructured":"Lagarias, J.C.: The computational complexity of simultaneous Diophantine approximation problems. SIAM Journal on Computing\u00a014, 196\u2013209 (1985)","journal-title":"SIAM Journal on Computing"},{"key":"30_CR24","doi-asserted-by":"publisher","first-page":"681","DOI":"10.1287\/mnsc.11.7.681","volume":"11","author":"C.E. Lemke","year":"1965","unstructured":"Lemke, C.E.: Bimatrix equilibrium points and mathematical programming. Management Science\u00a011, 681\u2013689 (1965)","journal-title":"Management Science"},{"key":"30_CR25","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/BF01580671","volume":"10","author":"O.L. Mangasarian","year":"1976","unstructured":"Mangasarian, O.L.: Linear complementarity problems solvable by a single linear program. Mathematical Programming\u00a010, 263\u2013270 (1976)","journal-title":"Mathematical Programming"},{"key":"30_CR26","unstructured":"Murty, K.G.: Linear Complementarity, Linear and Nonlinear Programming. Internet Edition (1997)"},{"key":"30_CR27","first-page":"805","volume":"9","author":"H. Samelson","year":"1958","unstructured":"Samelson, H., Thrall, R.M., Wesler, O.: A partition theorem for Euclidean n-space. Proceedings of the American Mathematical Society\u00a09, 805\u2013807 (1958)","journal-title":"Proceedings of the American Mathematical Society"},{"key":"30_CR28","doi-asserted-by":"crossref","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: Proceedings of the 10th Annual ACM Symposium on Theory of Computing, pp. 216\u2013226 (1978)","DOI":"10.1145\/800133.804350"},{"key":"30_CR29","doi-asserted-by":"publisher","first-page":"769","DOI":"10.1145\/322276.322288","volume":"28","author":"R. Shostak","year":"1981","unstructured":"Shostak, R.: Deciding linear inequalities by computing loop residues. Journal of the ACM\u00a028, 769\u2013779 (1981)","journal-title":"Journal of the ACM"},{"key":"30_CR30","doi-asserted-by":"crossref","unstructured":"Sumita, H., Kakimura, N., Makino, K.: Sparse linear complementarity problems. METR 2013-02, Department of Mathematical Informatics, University of Tokyo (2013)","DOI":"10.1007\/978-3-642-38233-8_30"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Complexity"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-38233-8_30","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,13]],"date-time":"2019-05-13T01:43:46Z","timestamp":1557711826000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-38233-8_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642382321","9783642382338"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-38233-8_30","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}