# Computing and proving with pivots

• Volume: 47, Issue: 4, page 331-360
• ISSN: 0399-0559

top

## Abstract

top
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.

## How to cite

top

Meunier, Frédéric. "Computing and proving with pivots." RAIRO - Operations Research - Recherche Opérationnelle 47.4 (2013): 331-360. <http://eudml.org/doc/275079>.

@article{Meunier2013,
abstract = {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.},
author = {Meunier, Frédéric},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
keywords = {combinatorial topology; complementarity problems; constructive proofs; pivoting algorithms},
language = {eng},
number = {4},
pages = {331-360},
publisher = {EDP-Sciences},
title = {Computing and proving with pivots},
url = {http://eudml.org/doc/275079},
volume = {47},
year = {2013},
}

TY - JOUR
AU - Meunier, Frédéric
TI - Computing and proving with pivots
JO - RAIRO - Operations Research - Recherche Opérationnelle
PY - 2013
PB - EDP-Sciences
VL - 47
IS - 4
SP - 331
EP - 360
AB - 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.
LA - eng
KW - combinatorial topology; complementarity problems; constructive proofs; pivoting algorithms
UR - http://eudml.org/doc/275079
ER -

## References

top
1. [1] R. Aharoni and T. Fleiner, On a lemma of Scarf. J. Comb. Theor. Ser. B87 (2003) 72–80. Zbl1058.05031MR1967882
2. [2] R. Aharoni and P. Haxell, Hall’s theorem for hypergraphs. J. Graph Theory35 (2000) 83–88. Zbl0956.05075MR1781189
3. [3] R. Aharoni and R. Holzman, Fractional kernels in digraphs. J. Comb. Theor. Ser. B73 (1998) 1–6. Zbl0904.05036MR1620603
4. [4] C. Berge and P. Duchet, Séminaire MSH. Paris (1983).
5. [5] E. Boros and V. Gurvich, Perfect graphs are kernel solvable. Discrete Math.159 (1996) 35–55. Zbl0861.05053MR1415280
6. [6] X. Cheng and X. Deng, On the complexity of 2d discrete fixed point problem. Theor. Comput. Sci.410 (2009) 448–4456. Zbl1183.68294MR2561571
7. [7] V. Chvátal, Linear programming. W.H. Freeman; 1st edn. (1983). Zbl0537.90067
8. [8] J. Cloutier, K.L. Nyman and F.E. Su, Two-player envy-free multi-cake division. Math. Soc. Sci.59 (2010) 26–37. Zbl1200.91146MR2587345
9. [9] R. Cottle, J. Pang and R. Stone, The linear complementarity problem. Academic Press, Boston (1992). Zbl0757.90078MR1150683
10. [10] R.W. Cottle and G.B. Dantzig, A generalization of the linear complementary problem. J. Comb. Theor. Ser. B8 (1970) 79–90. Zbl0186.23806MR254064
11. [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. Zbl0045.09802MR56260
12. [12] M. De Longueville, A course in topological combinatorics. Springer (2012). Zbl1273.05001
13. [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. Zbl1093.05006MR2231090
14. [14] Antoine Deza, Sui Huang, Tamon Stephen and Tamás Terlaky, The colourful feasibility problem. Discrete Appl. Math.156 (2008) 2166–2177. Zbl1151.90487MR2437008
15. [15] B.C. Eaves, The linear complementary problem in mathematical programming. Tech. report, Department of Operations Research, Standford University, Standford, California (1969). Zbl0228.15004
16. [16] B.C. Eaves, Homotopies for the computation of fixed points. Math. Programm.3 (1972) 1–22. Zbl0276.55004MR303953
17. [17] B.C. Eaves and R. Saigal, Homotopies for computation of fixed points on unbounded regions. Math. Programm.3 (1972) 225–237. Zbl0258.65060MR314028
18. [18] J. Edmonds, Euler complexes, Research trends in combinatorial optimization. Springer (2009) 65–68. Zbl1274.90299MR2513311
19. [19] J. Edmonds and L. Sanità, On finding another room-partitioning of the vertices, Electron. Notes in Discrete Math.36 (2010) 1257–1264. Zbl1274.90302
20. [20] K. Fan, A generalization of Tucker’s combinatorial lemma with topological applications. Ann. Math.56 (1952) 128–140. Zbl0047.42004
21. [21] K. Fan, Combinatorial properties of certain simplicial and cubical vertex maps. Arch. Mathematiks11 (1960) 368–377. Zbl0144.22502MR117721
22. [22] R.M. Freud and J. Todd, A constructive proof of Tucker’s combinatorial lemma. J. Comb. Theor. Ser. A30 (1981) 321–325. Zbl0462.05026MR618536
23. [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). Zbl05912605MR2820908
24. [24] C.B. Garcia, A fixed point theorem including the last theorem of Poincaré. Math. Programm.8 (1975) 227–239. Zbl0336.55010MR418069
25. [25] C.B. Garcia and W.I. Zangwill, An approach to homotopy and degree theory. Math. Oper. Res.4 (1979) 390–405. Zbl0422.55001MR549125
26. [26] C.B. Garcia and W.I. Zangwill, Pathways to solutions, fixed points and equilibria. Prentice-Hall, Englewood Cliffs (1981). Zbl0512.90070
27. [27] M. Grigni, A Sperner lemma complete for PPA. Inform. Process. Lett.77 (1995) 255–259. Zbl0996.68082MR1818525
28. [28] B. Hanke, R. Sanyal, C. Schultz and G. Ziegler, Combinatorial Stokes formulas via minimal resolutions. J. Comb. Theor. Ser. A116 (2009) 404–420. Zbl1200.05025MR2475024
29. [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 Behavior38 (2002) 89–117. Zbl1013.91004MR1875928
30. [30] R. Jeroslow, The simplex algorithm with the pivot rule of maximizing criterion improvement. Discrete Math.4 (1973) 367–377. Zbl0254.90027MR371393
31. [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). Zbl1292.68076MR2648410
32. [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. Zbl0297.90047MR332165
33. [33] A. Krawczyk, The complexity of finding a second Hamiltonian cycle in cubic graphs. J. Comput. System Sci.58 (1999) 641–647. Zbl0939.68093MR1705086
34. [34] H.W. Kuhn, Some combinatorial lemmas in topology. IBM J.4 (1960) 518–524. Zbl0109.15603MR124038
35. [35] H.W. Kuhn, Approximate search for fixed points, in Computing methods in optimization problems 2. Academic Press, New York (1969). Zbl0195.49402MR263221
36. [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. Zbl0411.90061MR538124
37. [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. Zbl0447.65019MR547992
38. [38] C.E. Lemke, Bimatrix equilibrium points and equilibrium programming. Manage. Sci.11 (1965) 681–689. Zbl0139.13103MR189823
39. [39] C.E. Lemke and J.T. Howson, Equilibrium points of bimatrix games. J. Soc. Industr. Appl. Math.12 (1964) 413–423. Zbl0128.14804MR173556
40. [40] J. Matoušek, Using the Borsuk-Ulam theorem. Springer (2003). Zbl1016.05001MR1988723
41. [41] J. Matoušek and B. Gärtner, Understanding and using linear programming. Springer (2006). Zbl1133.90001
42. [42] F. Meunier, Configurations équilibrées, Ph.D. thesis, Université Joseph Fourier. Grenoble (2006).
43. [43] F. Meunier, A Zq-Fan formula. Tech. report, Laboratoire Leibniz, INPG, Grenoble (2006).
44. [44] F. Meunier, Discrete splittings of the necklace. Math. Oper. Res.33 (2008) 678–688. Zbl1232.05248MR2442647
45. [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). Zbl1275.52020MR3157461
46. [46] P. Monsky, On dividing a square into triangles. Am. Math. Monthly77 (1970) 161–164. Zbl0187.19701MR252233
47. [47] D.M. Morris, Lemke paths on simple polytopes. Math. Oper. Res.19 (1994) 780–789. Zbl0821.90116MR1304624
48. [48] J.M. Munkres, Elements of algebraic topology. Perseus Books (1995). Zbl0542.55001
49. [49] J.F. Nash, Equilibrium points in n-person games. Proc. Natl. Acad. Sci. USA36 (1950) 48–49. Zbl0036.01104MR31701
50. [50] J. Neyman, Un théorème d’existence. Compt. R. Math. Acad. Sci. de Paris222 (1946) 843–845. Zbl0060.28404MR15697
51. [51] M.J. Osborne and A. Rubinstein, A course in game theory. MIT Press (1994). Zbl1194.91003MR1301776
52. [52] D. Pálvölgyi, 2D-TUCKER is PPAD-complete. WINE, Lect. Note Comput. Sci. 5929 (2009) 569–574.
53. [53] C. Papadimitriou, On the complexity of the parity argument and other inefficient proofs of existence. J. Comput. Syst. Sci.48 (1994) 498–532. Zbl0806.68048MR1279412
54. [54] T. Prescott and F.E. Su, A constructive proof of Ky Fan’s generalization of Tucker’s lemma. J. Combi. Theor. Ser. A111 (2005) 257–265. Zbl1080.55005MR2156212
55. [55] R. Savani and B. von Stengel, Hard-to-solve bimatrix games. Econometrica74 (2006) 397–429. Zbl1145.91301MR2207396
56. [56] H. Scarf, The approximation of fixed points of a continuous mapping. SIAM J. Appl. Math.15 (1967) 1328–1343. Zbl0153.49401MR242483
57. [57] H. Scarf, The core of an n person game. Econometrica35 (1967) 50–69. Zbl0183.24003MR234735
58. [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). Zbl0524.90016
59. [59] L.S. Shapley, A note on the Lemke-Howson algorithm. Math. Programm. Study1 (1974) 175–189. Zbl0366.90133MR434471
60. [60] E. Sperner, Neuer Beweis für die Invarianz der Dimensionszahl und des Gebietes, Abh. Math. Sem. Univ. Hambourg6 (1928) 265–272. Zbl54.0614.01MR3069504JFM54.0614.01
61. [61] T. Terlaky and S. Zhang, Pivot rules for linear programming: A survey on recent theoretical developments. Annal. Operat. Res.46 (1993) 203–233. Zbl0793.90034MR1260019
62. [62] A.G. Thomason, Hamiltonian cycles and uniquely edge colourable graphs. Annal. Discrete Math.3 (1978) 259–268. Zbl0382.05039MR499124
63. [63] M.J. Todd, A generalized complementary pivoting algorithm. Math. Programm.6 (1974) 243–263. Zbl0285.90053MR391953
64. [64] M.J. Todd, Orientations in complementary pivot algorithms. Math. Oper. Res.1 (1976) 54–66. Zbl0457.90074MR462618
65. [65] A.W. Tucker, Some topological properties of disk and sphere, in Proc. of the First Canadian Mathematical Congress, University of Toronto Press (1946). Zbl0061.40305MR20254
66. [66] W.T. Tutte, On Hamiltonian circuits. J. London Math. Soc.21 (1946) 98–101. Zbl0061.41306MR19300
67. [67] L.A. Végh and B. von Stengel, Oriented Euler complexes and signed perfect matchings. Tech. report (2012).
68. [68] R. Živaljević, Oriented matroids and Ky Fan’s theorem. Combinatorica30 (2010) 471–484. Zbl1274.52035
69. [69] L.A. Wolsey, Cubical Sperner lemmas as applications of generalized complementary pivoting. J. Comb. Theor. Ser. A23 (1977) 78–87. Zbl0367.90125MR445493

## NotesEmbed?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.