On Chubanov's Method for Linear Programming

References

• Agmon S (1954) The relaxation method for linear inequalities. Canadian J. Math. 6:382–392.Crossref, Google Scholar
• Amaldi E, Hauser R (2005) Boundedness theorems for the relaxation method. Math. Oper. Res. 30(4):939–955.Link, Google Scholar
• Belloni A, Freund R, Vempala S (2009) An efficient rescaled perceptron algorithm for conic systems. Math. Oper. Res. 34(3):621–641.Link, Google Scholar
• Betke U (2004) Relaxation, new combinatorial and polynomial algorithms for the linear feasibility problem. Discrete Comput. Geom. 32(3):317–338.Crossref, Google Scholar
• Bixby RE, Ceria S, McZeal CM, Savelsbergh MWP (1998) An updated mixed integer programming library: MIPLIB 3.0. Optima 58:12–15.Google Scholar
• Chubanov S (2011) A polynomial relaxation-type algorithm for linear programming. Unpublished manuscript.Google Scholar
• Chubanov S (2012a) A strongly polynomial algorithm for linear systems having a binary solution. Math. Programming 134(3):533–570.Crossref, Google Scholar
• Chubanov S (2012b) A polynomial relaxation-type algorithm for linear programming. Unpublished manuscript.Google Scholar
• Goffin J-L (1980) The relaxation method for solving systems of linear inequalities. Math. Oper. Res. 5(3):388–414.Link, Google Scholar
• Goffin J-L (1982) On the nonpolynomiality of the relaxation method for systems of linear inequalities. Math. Programming 22(1):93–103.Crossref, Google Scholar
• Hoffman A, Mannos M, Sokolowsky D, Wiegmann N (1953) Computational experience in solving linear programs. J. Soc. Indust. Appl. Math. 1(1):17–33.Crossref, Google Scholar
• Kaczmarz S (1993) Approximate solution of systems of linear equations. Internat. J. Control 57(6):1269–1271. Originally published as Kaczmarz S (1937) Angenäherte auflösung von systemen linearer gleichungen. Bulletin Internat. de l'Academie Polonaise des Sciences et des Lettres. Classe des Sciences Mathématiques et Naturelles 35:355–357.Crossref, Google Scholar
• Koch T, Achterberg T, Andersen E, Bastert O, Berthold T, Bixby RE, Danna Eet al. (2011) MIPLIB 2010. Math. Programming Comput. 3(2):103–163.Crossref, Google Scholar
• Maurras J-F, Truemper K, Akgül M (1981) Polynomial algorithms for a class of linear programs. Math. Programming 21(2):121–136.Crossref, Google Scholar
• Motzkin TS, Schoenberg IJ (1954) The relaxation method for linear inequalities. Canadian J. Math. 6:393–404.Crossref, Google Scholar
• Needell D (2010) Randomized Kaczmarz solver for noisy linear systems. BIT 50(2):395–403.Crossref, Google Scholar
• Papadimitriou CH, Steiglitz K (1998) Combinatorial Optimization: Algorithms and Complexity (Dover Publications, Mineola, NY).Google Scholar
• Schrijver A (1986) Theory of Linear and Integer Programming, Wiley-Interscience Series in Discrete Mathematics (John Wiley & Sons, Chichester, UK).Google Scholar
• Strohmer T, Vershynin R (2009) A randomized Kaczmarz algorithm with exponential convergence. J. Fourier Anal. Appl. 15(2):262–278.Crossref, Google Scholar
• Tardos É (1986) A strongly polynomial algorithm to solve combinatorial linear programs. Oper. Res. 34(2):250–256.Link, Google Scholar
• Telgen J (1982) On relaxation methods for systems of linear inequalities. Eur. J. Oper. Res. 9(2):184–189.Crossref, Google Scholar
• Vavasis S, Ye Y (1996) A primal-dual interior point method whose running time depends only on the constraint matrix. Math. Programming 74(1):79–120.Crossref, Google Scholar