{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:04:46Z","timestamp":1750694686495,"version":"3.33.0"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2007,2,27]],"date-time":"2007-02-27T00:00:00Z","timestamp":1172534400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2008,7]]},"DOI":"10.1007\/s10107-007-0095-7","type":"journal-article","created":{"date-parts":[[2007,2,26]],"date-time":"2007-02-26T14:50:07Z","timestamp":1172501407000},"page":"101-114","source":"Crossref","is-referenced-by-count":34,"title":["A simple polynomial-time rescaling algorithm for solving linear programs"],"prefix":"10.1007","volume":"114","author":[{"given":"John","family":"Dunagan","sequence":"first","affiliation":[]},{"given":"Santosh","family":"Vempala","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2007,2,27]]},"reference":[{"issue":"3","key":"95_CR1","doi-asserted-by":"crossref","first-page":"382","DOI":"10.4153\/CJM-1954-037-2","volume":"6","author":"S. Agmon","year":"1954","unstructured":"Agmon S. (1954). The relaxation method for linear inequalities. Can. J. Math. 6(3): 382\u2013392","journal-title":"Can. J. Math."},{"issue":"4","key":"95_CR2","doi-asserted-by":"crossref","first-page":"540","DOI":"10.1145\/1008731.1008733","volume":"51","author":"D. Bertsimas","year":"2004","unstructured":"Bertsimas D. and Vempala S. (2004). Solving convex programs by random walks. J. ACM 51(4): 540\u2013556","journal-title":"J. ACM"},{"key":"95_CR3","unstructured":"Blum, A., Dunagan, J.: Smoothed Analysis of the Perceptron Algorithm for Linear Programming. In: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 905\u2013914 (2002)"},{"issue":"1","key":"95_CR4","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1007\/PL00013833","volume":"22","author":"A. Blum","year":"1998","unstructured":"Blum A., Frieze A., Kannan R. and Vempala S. (1998). A polynomial-time algorithm for learning noisy linear threshold functions. Algorithmica 22(1): 35\u201352","journal-title":"Algorithmica"},{"key":"95_CR5","doi-asserted-by":"crossref","unstructured":"Bylander, T.: Learning linear threshold functions in the presence of classification noise. In: Proceedings of the Workshop on Computational Learning Theory (1994)","DOI":"10.1145\/180139.181176"},{"key":"95_CR6","doi-asserted-by":"crossref","unstructured":"Cohen, E.: Learning noisy perceptrons by a perceptron in polynomial time. In: Proceedings of the Annual IEEE Symposium on the Foundations of Computer Science, pp. 514\u2013523 (1997)","DOI":"10.1109\/SFCS.1997.646140"},{"issue":"1","key":"95_CR7","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1007\/s101070100237","volume":"91","author":"F. Cucker","year":"2001","unstructured":"Cucker F. and Cheung D. (2001). A new condition number for linear programming. Math. Program. Ser. A 91(1): 163\u2013174","journal-title":"Math. Program. Ser. A"},{"key":"95_CR8","volume-title":"Linear Programming","author":"V. Chvatal","year":"1983","unstructured":"Chvatal V. (1983). Linear Programming. W.H. Freeman, San Francisco"},{"key":"95_CR9","unstructured":"Dunagan, J., Teng, S., Spielman, D.A.: Smoothed analysis of Renegar\u2019s condition number for linear programming. In: SIAM Conference on Optimization (2002)"},{"key":"95_CR10","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1007\/978-1-4757-3216-0_18","volume-title":"High Performance Optimization.","author":"R.M. Freund","year":"2000","unstructured":"Freund R.M. and Mizuno S. (2000). Interior point methods: current status and future directions. In: Frenk, H. (eds) High Performance Optimization., pp 441\u2013466. Kluwer, Dordrecht"},{"key":"95_CR11","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1007\/s10107990063a","volume":"86","author":"R.M. Freund","year":"1999","unstructured":"Freund R.M. and Vera J.R. (1999). Some characterizations and properties of the distance to ill-posedness and the condition measure of a conic linear system. Math. Program. 86: 225\u2013260","journal-title":"Math. Program."},{"key":"95_CR12","unstructured":"Forster, J.: A linear lower bound on the unbounded error probabilistic communication complexity. In: 16th Annual IEEE Conference on Computational Complexity (2001). http:\/\/ citeseer.nj.nec.com\/forster01linear.html"},{"key":"95_CR13","unstructured":"Goffin, J.-L.: On the finite convergence of the relaxation method for solving systems of inequalities. Ph.D Thesis (1971). Also research report of the Operations Research Center, University of California at Berkeley"},{"issue":"3","key":"95_CR14","doi-asserted-by":"crossref","first-page":"388","DOI":"10.1287\/moor.5.3.388","volume":"5","author":"J.-L. Goffin","year":"1980","unstructured":"Goffin J.-L. (1980). The relaxation method for solving systems of linear inequalities. Math. Oper. Res. 5(3): 388\u2013414","journal-title":"Math. Oper. Res."},{"key":"95_CR15","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-97881-4","volume-title":"Geometric algorithms and Combinatorial Optimization","author":"L. Gr\u00f6tchel","year":"1988","unstructured":"Gr\u00f6tchel L., Lovasz L. and Schrijver A. (1988). Geometric algorithms and Combinatorial Optimization. Springer, Berlin"},{"key":"95_CR16","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1007\/BF02579150","volume":"4","author":"N. Karmarkar","year":"1984","unstructured":"Karmarkar N. (1984). A new polynomial-time algorithm for linear programming. Combinatorica 4: 373\u2013396","journal-title":"Combinatorica"},{"key":"95_CR17","unstructured":"Khachiyan, L.G.: A polynomial algorithm in linear programming, (in Russian), Doklady Akedamii Nauk SSSR, vol. 244, pp. 1093\u20131096 (1979) (English translation: Soviet Mathematics Doklady, 20, 191\u2013194 1979)"},{"key":"95_CR18","unstructured":"Minsky, M.L., Papert, S.A.: Perceptrons: sn introduction to computational geometry (1969)"},{"issue":"3","key":"95_CR19","doi-asserted-by":"crossref","first-page":"506","DOI":"10.1137\/0805026","volume":"5","author":"J. Renegar","year":"1995","unstructured":"Renegar J. (1995). Incorporating condition measures into the complexity theory of linear programming. SIAM J Optim 5(3): 506\u2013524","journal-title":"SIAM J Optim"},{"key":"95_CR20","volume-title":"Principles of Neurodynamics","author":"F. Rosenblatt","year":"1962","unstructured":"Rosenblatt F. (1962). Principles of Neurodynamics. Spartan Books, New York"},{"key":"95_CR21","volume-title":"Theory of Linar and Integer Programming","author":"A. Schrijver","year":"1998","unstructured":"Schrijver A. (1998). Theory of Linar and Integer Programming. Wiley, New York"},{"issue":"5","key":"95_CR22","doi-asserted-by":"crossref","first-page":"1358","DOI":"10.1137\/S0097539798340928","volume":"31","author":"R. Servedio","year":"2002","unstructured":"Servedio R. (2002). On PAC learning using perceptron, winnow and a perceptron-like algorithm. SIAM J. Comput. 31(5): 1358\u20131369","journal-title":"SIAM J. Comput."},{"key":"95_CR23","doi-asserted-by":"crossref","unstructured":"Servedio, R.: Smooth boosting and learning with malicious noise. In: 14th Annual Conference on Computational Learning Theory, pp. 473\u2013489 (2001)","DOI":"10.1007\/3-540-44581-1_31"},{"key":"95_CR24","doi-asserted-by":"crossref","first-page":"94","DOI":"10.1007\/BF01071394","volume":"13","author":"N.Z. Shor","year":"1977","unstructured":"Shor N.Z. (1977). Cut-off method with space extension in convex programming problems. Cybernetics 13: 94\u201396","journal-title":"Cybernetics"},{"key":"95_CR25","unstructured":"Shor, N.Z.: Utilization of the operation of space dilation in the minimization of convex functions. Kibernetika 1, 6\u201312 (1970) English translation: Cybernetics, 1, 7\u201315"},{"key":"95_CR26","first-page":"291","volume":"73","author":"P.M. Vaidya","year":"1996","unstructured":"Vaidya P.M. (1996). A new algorithm for minimizing convex functions over convex sets. Math Program 73: 291\u2013341","journal-title":"Math Program"},{"key":"95_CR27","unstructured":"Yudin, D.B., Nemirovski, A.S.: Evaluation of the information complexity of mathematical programming problems (in Russian). Ekonomika i Matematicheskie Metody 12, 128\u2013142, (1976) (English translation: Matekon 13(2), 3\u201345 1976)"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-007-0095-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-007-0095-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-007-0095-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,14]],"date-time":"2025-01-14T05:43:52Z","timestamp":1736833432000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-007-0095-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,2,27]]},"references-count":27,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2008,7]]}},"alternative-id":["95"],"URL":"https:\/\/doi.org\/10.1007\/s10107-007-0095-7","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2007,2,27]]}}}