{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T16:33:51Z","timestamp":1649003631026},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2016,10,17]],"date-time":"2016-10-17T00:00:00Z","timestamp":1476662400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2017,9]]},"DOI":"10.1007\/s00453-016-0229-5","type":"journal-article","created":{"date-parts":[[2016,10,17]],"date-time":"2016-10-17T08:54:57Z","timestamp":1476694497000},"page":"42-65","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Parameterized Complexity of Sparse Linear Complementarity Problems"],"prefix":"10.1007","volume":"79","author":[{"given":"Hanna","family":"Sumita","sequence":"first","affiliation":[]},{"given":"Naonori","family":"Kakimura","sequence":"additional","affiliation":[]},{"given":"Kazuhisa","family":"Makino","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,10,17]]},"reference":[{"key":"229_CR1","doi-asserted-by":"crossref","unstructured":"Arvind, V., K\u00f6bler, J., Kuhnert, S., Tor\u00e1n, J.: Solving linear equations parameterized by Hamming weight. Algorithmica 75(2), 322\u2013338 (2016)","DOI":"10.1007\/s00453-015-0098-3"},{"key":"229_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":"229_CR3","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1016\/j.jcss.2009.04.001","volume":"75","author":"HL Bodlaender","year":"2009","unstructured":"Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels. J. Comput. Syst. Sci. 75, 423\u2013434 (2009)","journal-title":"J. Comput. Syst. Sci."},{"key":"229_CR4","doi-asserted-by":"crossref","unstructured":"Chen, X., Deng, X., Teng, S.: Sparse games are hard. In: Spirakis, P., Mavronicolas, M., Kontogiannis, S. (eds.) Internet and Network Economics: Second International Workshop, WINE 2006, Patras, Greece, December 15\u201317, pp. 262\u2013273. Springer, Berlin, Heidelberg (2006)","DOI":"10.1007\/11944874_24"},{"key":"229_CR5","doi-asserted-by":"crossref","first-page":"14:1","DOI":"10.1145\/1516512.1516516","volume":"56","author":"X Chen","year":"2009","unstructured":"Chen, X., Deng, X., Teng, S.: Settling the complexity of computing two-player Nash equilibria. J. ACM 56, 14:1\u201314:57 (2009)","journal-title":"J. ACM"},{"key":"229_CR6","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1007\/BF00940344","volume":"60","author":"SJ Chung","year":"1989","unstructured":"Chung, S.J.: NP-completeness of the linear complementarity problem. J. Optim. Theory Appl. 60, 393\u2013399 (1989)","journal-title":"J. Optim. Theory Appl."},{"key":"229_CR7","doi-asserted-by":"crossref","unstructured":"Codenotti, B., Leoncini, M., Resta, G.: Efficient computation of Nash equilibria for very sparse win\u2013lose bimatrix games. In: Azar, Y., Erlebach, T. (eds.) Algorithms\u2014ESA 2006: 14th Annual European Symposium, Zurich, Switzerland, September 11\u201313, pp. 232\u2013243. Springer, Berlin, Heidelberg (2006)","DOI":"10.1007\/11841036_23"},{"key":"229_CR8","doi-asserted-by":"crossref","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 J. Comput. 23, 1313\u20131347 (1994)","journal-title":"SIAM J. Comput."},{"key":"229_CR9","unstructured":"Cottle, R.W.: The principal pivoting method of quadratic programming. In: Mathematics of Decision Sciences, Part 1, pp. 142\u2013162. American Mathematical Society, R.I., Providence (1968)"},{"key":"229_CR10","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1016\/0024-3795(68)90052-9","volume":"1","author":"RW Cottle","year":"1968","unstructured":"Cottle, R.W., Dantzig, G.B.: Complementary pivot theory of mathematical programming. Linear Algebra Appl. 1, 103\u2013125 (1968)","journal-title":"Linear Algebra Appl."},{"key":"229_CR11","volume-title":"The Linear Complementarity Problem","author":"RW Cottle","year":"1992","unstructured":"Cottle, R.W., Pang, J.S., Stone, R.E.: The Linear Complementarity Problem. Academic Press, Boston (1992)"},{"key":"229_CR12","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1016\/j.tcs.2012.07.001","volume":"511","author":"P Damaschke","year":"2013","unstructured":"Damaschke, P.: Sparse solutions of sparse linear systems: fixed-parameter tractability and an application of complex group testing. Theor. Comput. Sci. 511, 137\u2013146 (2013)","journal-title":"Theor. Comput. Sci."},{"key":"229_CR13","doi-asserted-by":"crossref","unstructured":"Daskalakis, C., Papadimitriou, C.H.: On oblivious PTAS\u2019s for Nash equilibrium. In: Mitzenmacher, M. (ed.) Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC \u201909, Bethesda, MD, USA, May 31\u2013June 02, pp. 75\u201384. ACM, New York (2009)","DOI":"10.1145\/1536414.1536427"},{"key":"229_CR14","doi-asserted-by":"crossref","unstructured":"Downey, R.G., Fellows, M.R.: Fixed-parameter intractability. In: Proceedings of the 7th Annual Structure in Complexity Theory Conference, Boston, MA, June 22\u201325, pp. 36\u201349. IEEE Computer Society Press, Los Alamitos, California (1992)","DOI":"10.1109\/SCT.1992.215379"},{"key":"229_CR15","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"RG Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, New York (1999)"},{"key":"229_CR16","unstructured":"Estivill-Castro, V., Parsa, M.: Computing Nash equilibria gets harder: new results show hardness even for parameterized complexity. In: Downey, R., Manyem, P. (eds.) Proceedings of the 15th Australasian Symposium on Computing: The Australasian Theory, CATS \u201909, Wellington, New Zealand, vol. 94, pp. 83\u201390. Australian Computer Society, Inc., Darlinghurst, Australia (2009)"},{"key":"229_CR17","volume-title":"Parameterized Complexity Theory","author":"J Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Berlin (2006)"},{"key":"229_CR18","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1016\/0899-8256(89)90006-7","volume":"1","author":"I Gilboa","year":"1989","unstructured":"Gilboa, I., Zemel, E.: Nash and correlated equilibria: some complexity considerations. Games Econ. Behav. 1, 80\u201393 (1989)","journal-title":"Games Econ. Behav."},{"key":"229_CR19","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00453-011-9571-9","volume":"65","author":"D Hermelin","year":"2013","unstructured":"Hermelin, D., Huang, C., Kratsch, S., Wahlstr\u00f6m, M.: Parameterized two-player Nash equilibrium. Algorithmica 65, 1\u201315 (2013)","journal-title":"Algorithmica"},{"key":"229_CR20","doi-asserted-by":"crossref","first-page":"1179","DOI":"10.1137\/S0097539793251876","volume":"23","author":"DS Hochbaum","year":"1994","unstructured":"Hochbaum, D.S., Naor, J.: Simple and fast algorithms for linear and integer programs with two variables per inequality. SIAM J. Comput. 23, 1179\u20131192 (1994)","journal-title":"SIAM J. Comput."},{"key":"229_CR21","doi-asserted-by":"crossref","unstructured":"Kratsch, S.: On polynomial kernels for integer linear programs: covering, packing and feasibility. In: Bodlaender, H.L., Italiano, G.F. (eds.) Algorithms\u2014ESA 2013: 21st Annual European Symposium, Sophia Antipolis, France, September 2\u20134, pp. 647\u2013658. Springer, Berlin, Heidelberg (2013)","DOI":"10.1007\/978-3-642-40450-4_55"},{"key":"229_CR22","doi-asserted-by":"crossref","unstructured":"Kratsch, S.: On polynomial kernels for sparse integer linear programs. J. Comput. Syst. Sci. 82(5), 758\u2013766 (2016)","DOI":"10.1016\/j.jcss.2015.12.002"},{"key":"229_CR23","doi-asserted-by":"crossref","unstructured":"Kratsch, S., Quyen, V.A.: On kernels for covering and packing ILPs with small coefficients. In: Cygan, M., Heggernes, P. (eds.) Parameterized and Exact Computation: 9th International Symposium, IPEC 2014, Wroclaw, Poland, September 10\u201312, pp. 307\u2013318. Springer International Publishing, Cham (2014)","DOI":"10.1007\/978-3-319-13524-3_26"},{"key":"229_CR24","doi-asserted-by":"crossref","first-page":"681","DOI":"10.1287\/mnsc.11.7.681","volume":"11","author":"CE Lemke","year":"1965","unstructured":"Lemke, C.E.: Bimatrix equilibrium points and mathematical programming. Manag. Sci. 11, 681\u2013689 (1965)","journal-title":"Manag. Sci."},{"key":"229_CR25","unstructured":"Murty, K.G.: Linear Complementarity, Linear and Nonlinear Programming (Internet Edition). \n                        http:\/\/ioe.engin.umich.edu\/people\/fac\/books\/murty\/linear_complementarity_webbook\/lcp-complete.pdf\n                        \n                     (1997). Accessed 11 Oct 2016"},{"key":"229_CR26","doi-asserted-by":"crossref","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: Lipton, R.J., Burkhard, W., Savitch, W., Friedman, E.P., Aho, A. (eds.) Proceedings of the 10th Annual ACM Symposium on Theory of Computing, STOC \u201978, San Diego, California, USA, pp. 216\u2013226. ACM, New York (1978)","DOI":"10.1145\/800133.804350"},{"key":"229_CR27","doi-asserted-by":"crossref","first-page":"1015","DOI":"10.1287\/moor.2014.0708","volume":"40","author":"H Sumita","year":"2015","unstructured":"Sumita, H., Kakimura, N., Makino, K.: The linear complementarity problems with a few variables per constraint. Math. Oper. Res. 40, 1015\u20131026 (2015)","journal-title":"Math. Oper. Res."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-016-0229-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0229-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0229-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,7,18]],"date-time":"2017-07-18T12:20:43Z","timestamp":1500380443000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-016-0229-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,10,17]]},"references-count":27,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,9]]}},"alternative-id":["229"],"URL":"https:\/\/doi.org\/10.1007\/s00453-016-0229-5","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,10,17]]}}}