A simple idea used in many combinatorial algorithms is the idea of pivoting. Originally, it comes from the method proposed by Gauss in the 19th century for solving systems of linear equations. This method had been extended in 1947 by Dantzig for the famous simplex algorithm used for solving linear programs. From since, a pivoting algorithm is a method exploring subsets of a ground set and going from one subset σ to a new one σ′ by deleting an element inside σ and adding an element outside σ: σ′ = σ\ { v} ∪ {u}, with v ∈ σ and u ∉ σ. This simple principle combined with other ideas appears to be quite powerful for many problems. This present paper is a survey on algorithms in operations research and discrete mathematics using pivots. We give also examples where this principle allows not only to compute but also to prove some theorems in a constructive way. A formalisation is described, mainly based on ideas by Michael J. Todd.

Keywords: combinatorial topology, complementarity problems, constructive proofs, pivoting algorithms

@article{RO_2013__47_4_331_0, author = {Meunier, Fr\'ed\'eric}, title = {Computing and proving with pivots}, journal = {RAIRO - Operations Research - Recherche Op\'erationnelle}, pages = {331--360}, publisher = {EDP-Sciences}, volume = {47}, number = {4}, year = {2013}, doi = {10.1051/ro/2013042}, mrnumber = {3143757}, zbl = {1286.90167}, language = {en}, url = {http://archive.numdam.org/articles/10.1051/ro/2013042/} }

TY - JOUR AU - Meunier, Frédéric TI - Computing and proving with pivots JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2013 SP - 331 EP - 360 VL - 47 IS - 4 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ro/2013042/ DO - 10.1051/ro/2013042 LA - en ID - RO_2013__47_4_331_0 ER -

Meunier, Frédéric. Computing and proving with pivots. RAIRO - Operations Research - Recherche Opérationnelle, Volume 47 (2013) no. 4, pp. 331-360. doi : 10.1051/ro/2013042. http://archive.numdam.org/articles/10.1051/ro/2013042/

[1] On a lemma of Scarf. J. Comb. Theor. Ser. B 87 (2003) 72-80. | MR | Zbl

and ,[2] Hall's theorem for hypergraphs. J. Graph Theory 35 (2000) 83-88. | MR | Zbl

and ,[3] Fractional kernels in digraphs. J. Comb. Theor. Ser. B 73 (1998) 1-6. | MR | Zbl

and ,[4] Séminaire MSH. Paris (1983).

and ,[5] Perfect graphs are kernel solvable. Discrete Math. 159 (1996) 35-55. | MR | Zbl

and ,[6] On the complexity of 2d discrete fixed point problem. Theor. Comput. Sci. 410 (2009) 448-4456. | MR | Zbl

and ,[7] Linear programming. W.H. Freeman; 1st edn. (1983). | Zbl

,[8] Two-player envy-free multi-cake division. Math. Soc. Sci. 59 (2010) 26-37. | MR | Zbl

, and ,[9] The linear complementarity problem. Academic Press, Boston (1992). | MR | Zbl

, and ,[10] A generalization of the linear complementary problem. J. Comb. Theor. Ser. B 8 (1970) 79-90. | MR | Zbl

and ,[11] Maximization of a linear function of variables subject to linear inequalities, in Activity analysis of production and allocation, edited by T.C. Koopmans. Wiley and Chapman-Hall (1947) 339-347. | MR | Zbl

,[12] A course in topological combinatorics. Springer (2012). | MR | Zbl

,[13] The Borsuk-Ulam-property, Tucker-property and constructive proofs in combinatorics. J. Comb. Theor. Ser. A 113 (2006) 839-850. | MR | Zbl

and ,[14] The colourful feasibility problem. Discrete Appl. Math. 156 (2008) 2166-2177. | MR | Zbl

, , and ,[15] The linear complementary problem in mathematical programming. Tech. report, Department of Operations Research, Standford University, Standford, California (1969). | Zbl

,[16] Homotopies for the computation of fixed points. Math. Programm. 3 (1972) 1-22. | MR | Zbl

,[17] Homotopies for computation of fixed points on unbounded regions. Math. Programm. 3 (1972) 225-237. | MR | Zbl

and ,[18] Euler complexes, Research trends in combinatorial optimization. Springer (2009) 65-68. | MR | Zbl

,[19] On finding another room-partitioning of the vertices, Electron. Notes in Discrete Math. 36 (2010) 1257-1264. | Zbl

and ,[20] A generalization of Tucker's combinatorial lemma with topological applications. Ann. Math. 56 (1952) 128-140. | MR | Zbl

,[21] Combinatorial properties of certain simplicial and cubical vertex maps. Arch. Mathematiks 11 (1960) 368-377. | MR | Zbl

,[22] A constructive proof of Tucker's combinatorial lemma. J. Comb. Theor. Ser. A 30 (1981) 321-325. | MR | Zbl

and ,[23] A subexponential lower bound for Zadeh's pivoting rule for solving linear programs and games, in Proc. of the 15th Conference on Integer Programming and Combinatorial Optimization, IPCO'11. New York, NY, USA (2011). | MR | Zbl

,[24] A fixed point theorem including the last theorem of Poincaré. Math. Programm. 8 (1975) 227-239. | MR | Zbl

,[25] An approach to homotopy and degree theory. Math. Oper. Res. 4 (1979) 390-405. | MR | Zbl

and ,[26] Pathways to solutions, fixed points and equilibria. Prentice-Hall, Englewood Cliffs (1981). | Zbl

and ,[27] A Sperner lemma complete for PPA. Inform. Process. Lett. 77 (1995) 255-259. | MR | Zbl

,[28] Combinatorial Stokes formulas via minimal resolutions. J. Comb. Theor. Ser. A 116 (2009) 404-420. | MR | Zbl

, , and ,[29] Computation of the Nash equilibrium selected by the tracing procedure in n-person games. Games and Economic Behavior 38 (2002) 89-117. | MR | Zbl

and ,[30] The simplex algorithm with the pivot rule of maximizing criterion improvement. Discrete Math. 4 (1973) 367-377. | MR | Zbl

,[31] Reducibility among fractional stability problems. IEEE Symposium Found. Comput. Sci. FOCS (2009). | MR | Zbl

, , , and ,[32] How good is the simplex method?, Inequalities III, in Proc. of Third Sympos. (New York), Univ. California, CA, 1969. Academic Press (1972) 159-175. | MR | Zbl

and ,[33] The complexity of finding a second Hamiltonian cycle in cubic graphs. J. Comput. System Sci. 58 (1999) 641-647. | MR | Zbl

,[34] Some combinatorial lemmas in topology. IBM J. 4 (1960) 518-524. | MR | Zbl

,[35] Approximate search for fixed points, in Computing methods in optimization problems 2. Academic Press, New York (1969). | MR | Zbl

,[36] A restart algorithm for computing fixed points without an extra dimension. Math. Programm. 17 (1979) 74-84. | MR | Zbl

and ,[37] A restart algorithm without an artificial level for computing fixed points on unbounded regions, in Functional differential equations and approximation of fixed points, edited by H.O. Peitgen and M.O. Walther. Springer-Verlag, Berlin (1979) 247-256. | MR | Zbl

and ,[38] Bimatrix equilibrium points and equilibrium programming. Manage. Sci. 11 (1965) 681-689. | MR | Zbl

,[39] Equilibrium points of bimatrix games. J. Soc. Industr. Appl. Math. 12 (1964) 413-423. | MR | Zbl

and ,[40] Using the Borsuk-Ulam theorem. Springer (2003). | MR | Zbl

,[41] Understanding and using linear programming. Springer (2006). | Zbl

and ,[42] Configurations équilibrées, Ph.D. thesis, Université Joseph Fourier. Grenoble (2006).

,[43] A Zq-Fan formula. Tech. report, Laboratoire Leibniz, INPG, Grenoble (2006).

,[44] Discrete splittings of the necklace. Math. Oper. Res. 33 (2008) 678-688. | MR | Zbl

,[45] A further generalization of the colourful Carathéodory theorem, Discrete Geometry and Optimization. Fields Institute Communications 69 (2013). | MR | Zbl

and ,[46] On dividing a square into triangles. Am. Math. Monthly 77 (1970) 161-164. | MR | Zbl

,[47] Lemke paths on simple polytopes. Math. Oper. Res. 19 (1994) 780-789. | MR | Zbl

,[48] Elements of algebraic topology. Perseus Books (1995). | Zbl

,[49] Equilibrium points in n-person games. Proc. Natl. Acad. Sci. USA 36 (1950) 48-49. | MR | Zbl

,[50] Un théorème d'existence. Compt. R. Math. Acad. Sci. de Paris 222 (1946) 843-845. | MR | Zbl

,[51] A course in game theory. MIT Press (1994). | MR | Zbl

and ,[52] 2D-TUCKER is PPAD-complete. WINE, Lect. Note Comput. Sci. 5929 (2009) 569-574.

,[53] On the complexity of the parity argument and other inefficient proofs of existence. J. Comput. Syst. Sci. 48 (1994) 498-532. | MR | Zbl

,[54] A constructive proof of Ky Fan's generalization of Tucker's lemma. J. Combi. Theor. Ser. A 111 (2005) 257-265. | MR | Zbl

and ,[55] Hard-to-solve bimatrix games. Econometrica 74 (2006) 397-429. | MR | Zbl

and ,[56] The approximation of fixed points of a continuous mapping. SIAM J. Appl. Math. 15 (1967) 1328-1343. | MR | Zbl

,[57] The core of an n person game. Econometrica 35 (1967) 50-69. | MR | Zbl

,[58] The computation of equilibrium prices: an exposition. in Handbook of mathematical economics, vol II, edited by K. Arrow and A. Kirman (1982). | Zbl

,[59] A note on the Lemke-Howson algorithm. Math. Programm. Study 1 (1974) 175-189. | MR | Zbl

,[60] Neuer Beweis für die Invarianz der Dimensionszahl und des Gebietes, Abh. Math. Sem. Univ. Hambourg 6 (1928) 265-272. | JFM | MR

,[61] Pivot rules for linear programming: A survey on recent theoretical developments. Annal. Operat. Res. 46 (1993) 203-233. | MR | Zbl

and ,[62] Hamiltonian cycles and uniquely edge colourable graphs. Annal. Discrete Math. 3 (1978) 259-268. | MR | Zbl

,[63] A generalized complementary pivoting algorithm. Math. Programm. 6 (1974) 243-263. | MR | Zbl

,[64] Orientations in complementary pivot algorithms. Math. Oper. Res. 1 (1976) 54-66. | MR | Zbl

,[65] Some topological properties of disk and sphere, in Proc. of the First Canadian Mathematical Congress, University of Toronto Press (1946). | MR | Zbl

,[66] On Hamiltonian circuits. J. London Math. Soc. 21 (1946) 98-101. | MR | Zbl

,[67] Oriented Euler complexes and signed perfect matchings. Tech. report (2012).

and ,[68] Oriented matroids and Ky Fan's theorem. Combinatorica 30 (2010) 471-484. | Zbl

,[69] Cubical Sperner lemmas as applications of generalized complementary pivoting. J. Comb. Theor. Ser. A 23 (1977) 78-87. | MR | Zbl

,*Cited by Sources: *