{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,14]],"date-time":"2025-06-14T01:40:13Z","timestamp":1749865213885},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2009,5,12]],"date-time":"2009-05-12T00:00:00Z","timestamp":1242086400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2009,9]]},"DOI":"10.1007\/s00454-009-9182-2","type":"journal-article","created":{"date-parts":[[2009,5,11]],"date-time":"2009-05-11T11:55:01Z","timestamp":1242042901000},"page":"187-205","source":"Crossref","is-referenced-by-count":7,"title":["Pivoting in Linear Complementarity: Two\u00a0Polynomial-Time Cases"],"prefix":"10.1007","volume":"42","author":[{"given":"Jan","family":"Foniok","sequence":"first","affiliation":[]},{"given":"Komei","family":"Fukuda","sequence":"additional","affiliation":[]},{"given":"Bernd","family":"G\u00e4rtner","sequence":"additional","affiliation":[]},{"given":"Hans-Jakob","family":"L\u00fcthi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2009,5,12]]},"reference":[{"issue":"4","key":"9182_CR1","doi-asserted-by":"crossref","first-page":"464","DOI":"10.1002\/rsa.20127","volume":"30","author":"J. Balogh","year":"2007","unstructured":"Balogh, J., Pemantle, R.: The Klee\u2013Minty random edge chain moves with linear speed. Random Struct. Algorithms 30(4), 464\u2013483 (2007)","journal-title":"Random Struct. Algorithms"},{"key":"9182_CR2","first-page":"116","volume-title":"Optimization, Proc. Sem. Austral. Nat. Univ.","author":"Y. Bard","year":"1972","unstructured":"Bard, Y.: An eclectic approach to nonlinear programming. In: Optimization, Proc. Sem. Austral. Nat. Univ., Canberra, 1971, pp. 116\u2013128. University of Queensland Press, St. Lucia (1972)"},{"key":"9182_CR3","series-title":"Applied Optimization","volume-title":"Computational Methods in Decision-Making, Economics and Finance","author":"A. Borici","year":"2002","unstructured":"Borici, A., L\u00fcthi, H.-J.: Pricing American put options by fast solutions of the linear complementarity problem. In: Kontoghiorghes, E.J., Rustem, B., Siokos, S. (eds.) Computational Methods in Decision-Making, Economics and Finance. Applied Optimization, vol. 74. Kluwer Academic, Dordrecht (2002)"},{"key":"9182_CR4","doi-asserted-by":"crossref","first-page":"63","DOI":"10.21314\/JCF.2005.126","volume":"9","author":"A. Borici","year":"2005","unstructured":"Borici, A., L\u00fcthi, H.-J.: Fast solutions of complementarity formulations in American put pricing. J.\u00a0Comput. Finance 9, 63\u201382 (2005)","journal-title":"J.\u00a0Comput. Finance"},{"key":"9182_CR5","first-page":"263","volume":"7","author":"R. Chandrasekaran","year":"1970","unstructured":"Chandrasekaran, R.: A special case of the complementary pivot problem. Opsearch 7, 263\u2013268 (1970)","journal-title":"Opsearch"},{"key":"9182_CR6","unstructured":"Chen, X., Deng, X.: Settling the complexity of 2-player Nash-equilibrium. Technical report TR05-140. Electronic colloquium on computational complexity (2005)"},{"issue":"3","key":"9182_CR7","doi-asserted-by":"crossref","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. J. Optim. Theory Appl. 60(3), 393\u2013399 (1989)","journal-title":"J. Optim. Theory Appl."},{"key":"9182_CR8","series-title":"Computer Science and Scientific Computing","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. Computer Science and Scientific Computing. Academic Press, New York (1992)"},{"key":"9182_CR9","volume-title":"Linear Programming and Extensions","author":"G.B. Dantzig","year":"1963","unstructured":"Dantzig, G.B.: Linear Programming and Extensions. Princeton University Press, Princeton (1963)"},{"issue":"4","key":"9182_CR10","doi-asserted-by":"crossref","first-page":"459","DOI":"10.1515\/advg.2004.4.4.459","volume":"4","author":"M. Develin","year":"2004","unstructured":"Develin, M.: LP-orientations of cubes and crosspolytopes. Adv. Geom. 4(4), 459\u2013468 (2004)","journal-title":"Adv. Geom."},{"issue":"3","key":"9182_CR11","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1007\/BF01582581","volume":"64","author":"K. Fukuda","year":"1994","unstructured":"Fukuda, K., Namiki, M.: On extremal behaviors of Murty\u2019s least index method. Math. Program. Ser. A 64(3), 365\u2013370 (1994)","journal-title":"Math. Program. Ser. A"},{"issue":"1\u20133","key":"9182_CR12","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1016\/S0166-218X(97)00143-1","volume":"84","author":"K. Fukuda","year":"1998","unstructured":"Fukuda, K., Namiki, M., Tamura, A.: EP theorems and linear complementarity problems. Discrete Appl. Math. 84(1\u20133), 107\u2013119 (1998)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"9182_CR13","first-page":"45","volume":"35","author":"K. Fukuda","year":"1992","unstructured":"Fukuda, K., Terlaky, T.: Linear complementarity and oriented matroids. J. Oper. Res. Soc. Japan 35(1), 45\u201361 (1992)","journal-title":"J. Oper. Res. Soc. Japan"},{"issue":"3","key":"9182_CR14","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1002\/rsa.10034","volume":"20","author":"B. G\u00e4rtner","year":"2002","unstructured":"G\u00e4rtner, B.: The random-facet simplex algorithm on combinatorial cubes. Random Struct. Algorithms 20(3), 353\u2013381 (2002)","journal-title":"Random Struct. Algorithms"},{"issue":"2","key":"9182_CR15","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1007\/s00453-007-9090-x","volume":"51","author":"B. G\u00e4rtner","year":"2008","unstructured":"G\u00e4rtner, B., Morris, W.D., R\u00fcst, L.: Unique sink orientations of grids. Algorithmica 51(2), 200\u2013235 (2008)","journal-title":"Algorithmica"},{"key":"9182_CR16","series-title":"Contemporary Mathematics","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1090\/conm\/223\/03138","volume-title":"Advances in Discrete and Computational Geometry","author":"F. Holt","year":"1999","unstructured":"Holt, F., Klee, V.: A proof of the strict monotone 4-step conjecture. In: Advances in Discrete and Computational Geometry. Contemporary Mathematics, vol. 223, pp. 201\u2013216. Am. Math. Soc., Providence (1999)"},{"issue":"4","key":"9182_CR17","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1007\/BF02579150","volume":"4","author":"N. Karmarkar","year":"1984","unstructured":"Karmarkar, N.: A new polynomial-time algorithm for linear programming. Combinatorica 4(4), 373\u2013395 (1984)","journal-title":"Combinatorica"},{"key":"9182_CR18","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/0041-5553(80)90061-0","volume":"20","author":"L.G. Khachiyan","year":"1980","unstructured":"Khachiyan, L.G.: Polynomial algorithms in linear programming. USSR Comput. Math. Math. Phys. 20, 53\u201372 (1980)","journal-title":"USSR Comput. Math. Math. Phys."},{"key":"9182_CR19","first-page":"159","volume-title":"Inequalities","author":"V. Klee","year":"1972","unstructured":"Klee, V., Minty, G.J.: How good is the simplex algorithm? In: Shisha, O. (ed.) Inequalities, vol.\u00a0III, pp.\u00a0159\u2013175. Academic Press, New York (1972)"},{"key":"9182_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","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. Lecture Notes in Computer Science, vol.\u00a0538. Springer, Berlin (1991)"},{"issue":"3","key":"9182_CR21","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1007\/BF01586054","volume":"54","author":"M. Kojima","year":"1992","unstructured":"Kojima, M., Megiddo, N., Ye, Y.: An interior point potential reduction algorithm for the linear complementarity problem. Math. Program. Ser. A 54(3), 267\u2013279 (1992)","journal-title":"Math. Program. Ser. A"},{"key":"9182_CR22","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1016\/B978-0-12-597050-1.50016-6","volume-title":"Nonlinear Programming","author":"C.E. Lemke","year":"1970","unstructured":"Lemke, C.E.: Recent results on complementarity problems. In: Nonlinear Programming, pp. 349\u2013384. Academic Press, New York (1970)"},{"key":"9182_CR23","unstructured":"Megiddo, N.: A note on the complexity of P-matrix LCP and computing an equilibrium. RJ 6439, IBM Research, Almaden Research Center, San Jose, CA (1988)"},{"issue":"2","key":"9182_CR24","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1007\/s101070100268","volume":"92","author":"W.D. Morris Jr.","year":"2002","unstructured":"Morris, W.D. Jr.: Randomized pivot algorithms for P-matrix linear complementarity problems. Math. Program. Ser. A 92(2), 285\u2013296 (2002)","journal-title":"Math. Program. Ser. A"},{"issue":"2\u20133","key":"9182_CR25","first-page":"123","volume":"11","author":"K.G. Murty","year":"1974","unstructured":"Murty, K.G.: Note on a Bard-type scheme for solving the complementarity problem. Opsearch 11(2\u20133), 123\u2013130 (1974)","journal-title":"Opsearch"},{"key":"9182_CR26","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1007\/BFb0120782","volume":"7","author":"K.G. Murty","year":"1978","unstructured":"Murty, K.G.: Computational complexity of complementary pivot methods. Math. Program. Stud. 7, 61\u201373 (1978)","journal-title":"Math. Program. Stud."},{"key":"9182_CR27","series-title":"Sigma Series in Applied Mathematics","volume-title":"Linear Complementarity, Linear and Nonlinear Programming","author":"K.G. Murty","year":"1988","unstructured":"Murty, K.G.: Linear Complementarity, Linear and Nonlinear Programming. Sigma Series in Applied Mathematics, vol.\u00a03. Heldermann, Berlin (1988)"},{"issue":"3","key":"9182_CR28","doi-asserted-by":"crossref","first-page":"498","DOI":"10.1016\/S0022-0000(05)80063-7","volume":"48","author":"C.H. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.H.: On the complexity of the parity argument and other inefficient proofs of existence. J. Comput. Syst. Sci. 48(3), 498\u2013532 (1994)","journal-title":"J. Comput. Syst. Sci."},{"key":"9182_CR29","first-page":"175","volume":"7","author":"R. Saigal","year":"1970","unstructured":"Saigal, R.: A note on a special linear complementarity problem. Opsearch 7, 175\u2013183 (1970)","journal-title":"Opsearch"},{"key":"9182_CR30","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. Proc. Am. Math. Soc. 9, 805\u2013807 (1958)","journal-title":"Proc. Am. Math. Soc."},{"issue":"4","key":"9182_CR31","doi-asserted-by":"crossref","first-page":"322","DOI":"10.1287\/moor.3.4.322","volume":"3","author":"A. Stickney","year":"1978","unstructured":"Stickney, A., Watson, L.: Digraph models of Bard-type algorithms for the linear complementarity problem. Math. Oper. Res. 3(4), 322\u2013333 (1978)","journal-title":"Math. Oper. Res."},{"key":"9182_CR32","doi-asserted-by":"crossref","unstructured":"Szab\u00f3, T., Welzl, E.: Unique sink orientations of cubes. In: Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science (FOCS\u201901), pp.\u00a0547\u2013555 (2001)","DOI":"10.1109\/SFCS.2001.959931"},{"key":"9182_CR33","unstructured":"Wessendorp, F.: Notes on Morris\u2019 cube orientation. Diploma thesis, ETH, Z\u00fcrich (March 2001)"},{"key":"9182_CR34","volume-title":"Methods of Feasible Directions: A Study in Linear and Non-Linear Programming","author":"G. Zoutendijk","year":"1960","unstructured":"Zoutendijk, G.: Methods of Feasible Directions: A Study in Linear and Non-Linear Programming. Elsevier, Amsterdam (1960)"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-009-9182-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-009-9182-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-009-9182-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,28]],"date-time":"2019-05-28T19:47:37Z","timestamp":1559072857000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-009-9182-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,5,12]]},"references-count":34,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2009,9]]}},"alternative-id":["9182"],"URL":"https:\/\/doi.org\/10.1007\/s00454-009-9182-2","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,5,12]]}}}