Computing and proving with pivots

Meunier, Frédéric

RAIRO - Operations Research - Recherche Opérationnelle, Tome 47 (2013) no. 4, pp. 331-360.

Résumé

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.

Détail

DOI : 10.1051/ro/2013042

Classification : 90C49, 05E45
Keywords: combinatorial topology, complementarity problems, constructive proofs, pivoting algorithms

Bibliographie

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

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

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

[4] C. Berge and P. Duchet, Séminaire MSH. Paris (1983).

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

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

[7] V. Chvátal, Linear programming. W.H. Freeman; 1st edn. (1983). | Zbl

[8] J. Cloutier, K.L. Nyman and F.E. Su, Two-player envy-free multi-cake division. Math. Soc. Sci. 59 (2010) 26-37. | Zbl | MR

[9] R. Cottle, J. Pang and R. Stone, The linear complementarity problem. Academic Press, Boston (1992). | Zbl | MR

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

[11] G.B. Dantzig, 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. | Zbl | MR

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

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

[14] Antoine Deza, Sui Huang, Tamon Stephen and Tamás Terlaky, The colourful feasibility problem. Discrete Appl. Math. 156 (2008) 2166-2177. | Zbl | MR

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

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

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

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

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

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

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

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

[23] O. Friedmann, 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] C.B. Garcia, A fixed point theorem including the last theorem of Poincaré. Math. Programm. 8 (1975) 227-239. | Zbl | MR

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

[26] C.B. Garcia and W.I. Zangwill, Pathways to solutions, fixed points and equilibria. Prentice-Hall, Englewood Cliffs (1981). | Zbl

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

[28] B. Hanke, R. Sanyal, C. Schultz and G. Ziegler, Combinatorial Stokes formulas via minimal resolutions. J. Comb. Theor. Ser. A 116 (2009) 404-420. | Zbl | MR

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

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

[31] 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). | Zbl | MR

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

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

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

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

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

[37] G. Van Der Laan and A.J.J. Talman, 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. | Zbl | MR

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

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

[40] J. Matoušek, Using the Borsuk-Ulam theorem. Springer (2003). | Zbl | MR

[41] J. Matoušek and B. Gärtner, Understanding and using linear programming. Springer (2006). | Zbl

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

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

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

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

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

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

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

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

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

[51] M.J. Osborne and A. Rubinstein, A course in game theory. MIT Press (1994). | Zbl | MR

[52] D. Pálvölgyi, 2D-TUCKER is PPAD-complete. WINE, Lect. Note Comput. Sci. 5929 (2009) 569-574.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[67] L.A. Végh and B. Von Stengel, Oriented Euler complexes and signed perfect matchings. Tech. report (2012).

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

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