{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T12:49:29Z","timestamp":1759063769617},"reference-count":69,"publisher":"EDP Sciences","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Oper. Res."],"published-print":{"date-parts":[[2013,10]]},"DOI":"10.1051\/ro\/2013042","type":"journal-article","created":{"date-parts":[[2013,10,9]],"date-time":"2013-10-09T08:05:33Z","timestamp":1381305933000},"page":"331-360","source":"Crossref","is-referenced-by-count":2,"title":["Computing and proving with pivots"],"prefix":"10.1051","volume":"47","author":[{"given":"Fr\u00e9d\u00e9ric","family":"Meunier","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"250","published-online":{"date-parts":[[2013,10,9]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"Aharoni R. and Fleiner T., On a lemma of Scarf.J. Comb. Theor. Ser. B87(2003) 72\u201380.","DOI":"10.1016\/S0095-8956(02)00028-X"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"Aharoni R. and Haxell P., Hall\u2019s theorem for hypergraphs.J. Graph Theory35(2000) 83\u201388.","DOI":"10.1002\/1097-0118(200010)35:2<83::AID-JGT2>3.0.CO;2-V"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"Aharoni R. and Holzman R., Fractional kernels in digraphs.J. Comb. Theor. Ser. B73(1998) 1\u20136.","DOI":"10.1006\/jctb.1997.1731"},{"key":"R4","unstructured":"C. Berge and P. Duchet,S\u00e9minaire MSH. Paris (1983)."},{"key":"R5","doi-asserted-by":"crossref","unstructured":"Boros E. and Gurvich V., Perfect graphs are kernel solvable.Discrete Math.159(1996) 35\u201355.","DOI":"10.1016\/0012-365X(95)00096-F"},{"key":"R6","unstructured":"Cheng X. and Deng X., On the complexity of 2d discrete fixed point problem.Theor. Comput. Sci.410(2009) 448\u20134456."},{"key":"R7","unstructured":"V. Chv\u00e1tal,Linear programming. W.H. Freeman; 1st edn. (1983)."},{"key":"R8","unstructured":"Cloutier J., Nyman K.L. and Su F.E., Two-player envy-free multi-cake division.Math. Soc. Sci.59(2010) 26\u201337."},{"key":"R9","unstructured":"R. Cottle, J. Pang and R. Stone,The linear complementarity problem. Academic Press, Boston (1992)."},{"key":"R10","doi-asserted-by":"crossref","unstructured":"Cottle R.W. and Dantzig G.B., A generalization of the linear complementary problem.J. Comb. Theor. Ser. B8(1970) 79\u201390.","DOI":"10.1016\/S0021-9800(70)80010-2"},{"key":"R11","unstructured":"G.B. Dantzig, Maximization of a linear function of variables subject to linear inequalities, inActivity analysis of production and allocation, edited by T.C. Koopmans. Wiley and Chapman-Hall (1947) 339\u2013347."},{"key":"R12","doi-asserted-by":"crossref","unstructured":"M. De Longueville,A course in topological combinatorics. Springer (2012).","DOI":"10.1007\/978-1-4419-7910-0"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"De Longueville M. and \u017divaljevic R., The Borsuk-Ulam-property, Tucker-property and constructive proofs in combinatorics.J. Comb. Theor. Ser. A113(2006) 839\u2013850.","DOI":"10.1016\/j.jcta.2005.08.002"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"Antoine Deza, Sui Huang, Tamon Stephen and Tam\u00e1s Terlaky, The colourful feasibility problem.Discrete Appl. Math.156(2008) 2166\u20132177.","DOI":"10.1016\/j.dam.2008.01.016"},{"key":"R15","unstructured":"B.C. Eaves,The linear complementary problem in mathematical programming. Tech. report, Department of Operations Research, Standford University, Standford, California (1969)."},{"key":"R16","unstructured":"Eaves B.C., Homotopies for the computation of fixed points.Math. Programm.3(1972) 1\u201322."},{"key":"R17","unstructured":"Eaves B.C. and Saigal R., Homotopies for computation of fixed points on unbounded regions.Math. Programm.3(1972) 225\u2013237."},{"key":"R18","doi-asserted-by":"crossref","unstructured":"J. Edmonds,Euler complexes, Research trends in combinatorial optimization. Springer (2009) 65\u201368.","DOI":"10.1007\/978-3-540-76796-1_4"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"Edmonds J. and Sanit\u00e0 L., On finding another room-partitioning of the vertices,Electron. Notes in Discrete Math.36(2010) 1257\u20131264.","DOI":"10.1016\/j.endm.2010.05.159"},{"key":"R20","unstructured":"Fan K., A generalization of Tucker\u2019s combinatorial lemma with topological applications.Ann. Math.56(1952) 128\u2013140."},{"key":"R21","doi-asserted-by":"crossref","unstructured":"Fan K., Combinatorial properties of certain simplicial and cubical vertex maps.Arch. Mathematiks11(1960) 368\u2013377.","DOI":"10.1007\/BF01236961"},{"key":"R22","doi-asserted-by":"crossref","unstructured":"Freud R.M. and Todd J., A constructive proof of Tucker\u2019s combinatorial lemma.J. Comb. Theor. Ser. A30(1981) 321\u2013325.","DOI":"10.1016\/0097-3165(81)90027-3"},{"key":"R23","doi-asserted-by":"crossref","unstructured":"O. Friedmann, A subexponential lower bound for Zadeh\u2019s pivoting rule for solving linear programs and games, inProc. of the 15th Conference on Integer Programming and Combinatorial Optimization, IPCO\u201911. New York, NY, USA (2011).","DOI":"10.1007\/978-3-642-20807-2_16"},{"key":"R24","unstructured":"Garcia C.B., A fixed point theorem including the last theorem of Poincar\u00e9.Math. Programm.8(1975) 227\u2013239."},{"key":"R25","unstructured":"Garcia C.B. and Zangwill W.I., An approach to homotopy and degree theory.Math. Oper. Res.4(1979) 390\u2013405."},{"key":"R26","unstructured":"C.B. Garcia and W.I. Zangwill,Pathways to solutions, fixed points and equilibria. Prentice-Hall, Englewood Cliffs (1981)."},{"key":"R27","doi-asserted-by":"crossref","unstructured":"Grigni M., A Sperner lemma complete for PPA.Inform. Process. Lett.77(1995) 255\u2013259.","DOI":"10.1016\/S0020-0190(00)00152-6"},{"key":"R28","doi-asserted-by":"crossref","unstructured":"Hanke B., Sanyal R., Schultz C. and Ziegler G., Combinatorial Stokes formulas via minimal resolutions.J. Comb. Theor. Ser. A116(2009) 404\u2013420.","DOI":"10.1016\/j.jcta.2008.06.009"},{"key":"R29","doi-asserted-by":"crossref","unstructured":"Herings P.J.-J. and van den Elzen A., Computation of the Nash equilibrium selected by the tracing procedure inn-person games.Games and Economic Behavior38(2002) 89\u2013117.","DOI":"10.1006\/game.2001.0856"},{"key":"R30","unstructured":"Jeroslow R., The simplex algorithm with the pivot rule of maximizing criterion improvement.Discrete Math.4(1973) 367\u2013377."},{"key":"R31","doi-asserted-by":"crossref","unstructured":"S. Kintali, L.J. Poplawski, R. Rajaraman, R. Sundaram and S.-H. Teng, Reducibility among fractional stability problems.IEEE Symposium Found. Comput. Sci. FOCS(2009).","DOI":"10.1109\/FOCS.2009.57"},{"key":"R32","unstructured":"V. Klee and G.J. Minty, How good is the simplex method?, Inequalities III, inProc. of Third Sympos. (New York), Univ. California, CA, 1969. Academic Press (1972) 159\u2013175."},{"key":"R33","doi-asserted-by":"crossref","unstructured":"Krawczyk A., The complexity of finding a second Hamiltonian cycle in cubic graphs.J. Comput. System Sci.58(1999) 641\u2013647.","DOI":"10.1006\/jcss.1998.1611"},{"key":"R34","unstructured":"Kuhn H.W., Some combinatorial lemmas in topology.IBM J.4(1960) 518\u2013524."},{"key":"R35","unstructured":"H.W. Kuhn, Approximate search for fixed points, inComputing methods in optimization problems 2. Academic Press, New York (1969)."},{"key":"R36","unstructured":"van der Laan G. and Talman A.J.J., A restart algorithm for computing fixed points without an extra dimension.Math. Programm.17(1979) 74\u201384."},{"key":"R37","doi-asserted-by":"crossref","unstructured":"G. van der Laan and A.J.J. Talman, A restart algorithm without an artificial level for computing fixed points on unbounded regions, inFunctional differential equations and approximation of fixed points, edited by H.O. Peitgen and M.O. Walther. Springer-Verlag, Berlin (1979) 247\u2013256.","DOI":"10.1007\/BFb0064322"},{"key":"R38","unstructured":"Lemke C.E., Bimatrix equilibrium points and equilibrium programming.Manage. Sci.11(1965) 681\u2013689."},{"key":"R39","doi-asserted-by":"crossref","unstructured":"Lemke C.E. and Howson J.T., Equilibrium points of bimatrix games.J. Soc. Industr. Appl. Math.12(1964) 413\u2013423.","DOI":"10.1137\/0112033"},{"key":"R40","unstructured":"J. Matou\u0161ek,Using the Borsuk-Ulam theorem. Springer (2003)."},{"key":"R41","unstructured":"J. Matou\u0161ek and B. G\u00e4rtner,Understanding and using linear programming. Springer (2006)."},{"key":"R42","unstructured":"F. Meunier,Configurations \u00e9quilibr\u00e9es, Ph.D. thesis, Universit\u00e9 Joseph Fourier. Grenoble (2006)."},{"key":"R43","unstructured":"F. Meunier,AZq-Fan formula. Tech. report, Laboratoire Leibniz, INPG, Grenoble (2006)."},{"key":"R44","doi-asserted-by":"crossref","unstructured":"Meunier F., Discrete splittings of the necklace.Math. Oper. Res.33(2008) 678\u2013688.","DOI":"10.1287\/moor.1080.0311"},{"key":"R45","doi-asserted-by":"crossref","unstructured":"Fr\u00e9d\u00e9ric Meunier and Antoine Deza, A further generalization of the colourful Carath\u00e9odory theorem, Discrete Geometry and Optimization.Fields Institute Communications69(2013).","DOI":"10.1007\/978-3-319-00200-2_11"},{"key":"R46","doi-asserted-by":"crossref","unstructured":"Monsky P., On dividing a square into triangles.Am. Math. Monthly77(1970) 161\u2013164.","DOI":"10.2307\/2317329"},{"key":"R47","doi-asserted-by":"crossref","unstructured":"Morris D.M., Lemke paths on simple polytopes.Math. Oper. Res.19(1994) 780\u2013789.","DOI":"10.1287\/moor.19.4.780"},{"key":"R48","unstructured":"J.M. Munkres,Elements of algebraic topology. Perseus Books (1995)."},{"key":"R49","doi-asserted-by":"crossref","unstructured":"Nash J.F., Equilibrium points inn-person games.Proc. Natl. Acad. Sci. USA36(1950) 48\u201349.","DOI":"10.1073\/pnas.36.1.48"},{"key":"R50","unstructured":"Neyman J., Un th\u00e9or\u00e8me d\u2019existence.Compt. R. Math. Acad. Sci. de Paris222(1946) 843\u2013845."},{"key":"R51","unstructured":"M.J. Osborne and A. Rubinstein,A course in game theory. MIT Press (1994)."},{"key":"R52","doi-asserted-by":"crossref","unstructured":"P\u00e1lv\u00f6lgyi D., 2D-TUCKER is PPAD-complete. WINE,Lect. Note Comput. Sci.5929(2009) 569\u2013574.","DOI":"10.1007\/978-3-642-10841-9_57"},{"key":"R53","doi-asserted-by":"crossref","unstructured":"Papadimitriou C., On the complexity of the parity argument and other inefficient proofs of existence.J. Comput. Syst. Sci.48(1994) 498\u2013532.","DOI":"10.1016\/S0022-0000(05)80063-7"},{"key":"R54","doi-asserted-by":"crossref","unstructured":"Prescott T. and Su F.E., A constructive proof of Ky Fan\u2019s generalization of Tucker\u2019s lemma.J. Combi. Theor. Ser. A111(2005) 257\u2013265.","DOI":"10.1016\/j.jcta.2004.12.005"},{"key":"R55","doi-asserted-by":"crossref","unstructured":"Savani R. and von Stengel B., Hard-to-solve bimatrix games.Econometrica74(2006) 397\u2013429.","DOI":"10.1111\/j.1468-0262.2006.00667.x"},{"key":"R56","unstructured":"Scarf H., The approximation of fixed points of a continuous mapping.SIAM J. Appl. Math.15(1967) 1328\u20131343."},{"key":"R57","doi-asserted-by":"crossref","unstructured":"Scarf H., The core of annperson game.Econometrica35(1967) 50\u201369.","DOI":"10.2307\/1909383"},{"key":"R58","unstructured":"H. Scarf, The computation of equilibrium prices: an exposition. inHandbook of mathematical economics, vol II, edited by K. Arrow and A. Kirman (1982)."},{"key":"R59","doi-asserted-by":"crossref","unstructured":"Shapley L.S., A note on the Lemke-Howson algorithm.Math. Programm. Study1(1974) 175\u2013189.","DOI":"10.1007\/BFb0121248"},{"key":"R60","doi-asserted-by":"crossref","unstructured":"Sperner E., Neuer Beweis f\u00fcr die Invarianz der Dimensionszahl und des Gebietes,Abh. Math. Sem. Univ. Hambourg6(1928) 265\u2013272.","DOI":"10.1007\/BF02940617"},{"key":"R61","doi-asserted-by":"crossref","unstructured":"Terlaky T. and Zhang S., Pivot rules for linear programming: A survey on recent theoretical developments.Annal. Operat. Res.46(1993) 203\u2013233.","DOI":"10.1007\/BF02096264"},{"key":"R62","unstructured":"Thomason A.G., Hamiltonian cycles and uniquely edge colourable graphs.Annal. Discrete Math.3(1978) 259\u2013268."},{"key":"R63","doi-asserted-by":"crossref","unstructured":"Todd M.J., A generalized complementary pivoting algorithm.Math. Programm.6(1974) 243\u2013263.","DOI":"10.1007\/BF01580244"},{"key":"R64","doi-asserted-by":"crossref","unstructured":"Todd M.J., Orientations in complementary pivot algorithms.Math. Oper. Res.1(1976) 54\u201366.","DOI":"10.1287\/moor.1.1.54"},{"key":"R65","unstructured":"A.W. Tucker, Some topological properties of disk and sphere, inProc. of the FirstCanadianMathematical Congress, University of Toronto Press (1946)."},{"key":"R66","doi-asserted-by":"crossref","unstructured":"Tutte W.T., On Hamiltonian circuits.J. London Math. Soc.21(1946) 98\u2013101.","DOI":"10.1112\/jlms\/s1-21.2.98"},{"key":"R67","unstructured":"L.A. V\u00e9gh and B. von Stengel, Oriented Euler complexes and signed perfect matchings.Tech. report(2012)."},{"key":"R68","doi-asserted-by":"crossref","unstructured":"\u017divaljevi\u0107 R., Oriented matroids and Ky Fan\u2019s theorem.Combinatorica30(2010) 471\u2013484.","DOI":"10.1007\/s00493-010-2446-x"},{"key":"R69","doi-asserted-by":"crossref","unstructured":"Wolsey L.A., Cubical Sperner lemmas as applications of generalized complementary pivoting.J. Comb. Theor. Ser. A23(1977) 78\u201387.","DOI":"10.1016\/0097-3165(77)90081-4"}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"http:\/\/www.rairo-ro.org\/10.1051\/ro\/2013042\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,30]],"date-time":"2019-07-30T14:58:13Z","timestamp":1564498693000},"score":1,"resource":{"primary":{"URL":"http:\/\/www.rairo-ro.org\/10.1051\/ro\/2013042"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,10]]},"references-count":69,"journal-issue":{"issue":"4"},"alternative-id":["ro130042"],"URL":"https:\/\/doi.org\/10.1051\/ro\/2013042","relation":{},"ISSN":["0399-0559","1290-3868"],"issn-type":[{"value":"0399-0559","type":"print"},{"value":"1290-3868","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,10]]}}}