Computing and proving with pivots

Frédéric Meunier

RAIRO - Operations Research - Recherche Opérationnelle (2013)

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

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.