Smoothed Analysis of Algorithms: Why the Simplex Algorithm Usually Takes Polynomial Time. Spielman, D. A. & Teng, S. Journal of the ACM (J. ACM), 51(3):385–463, ACM, New York, NY, USA, 2004. ![Smoothed Analysis of Algorithms: Why the Simplex Algorithm Usually Takes Polynomial Time [link]](https://bibbase.org/img/filetypes/link.svg "link")
Paper doi bibtex @article{ST04,
Acmid = {990310},
Address = {New York, NY, USA},
Author = {Spielman, Daniel A. and Teng, Shang-Hua},
Date-Added = {2014-11-14 04:05:47 +0000},
Date-Modified = {2014-11-14 04:06:31 +0000},
Doi = {10.1145/990308.990310},
Issn = {0004-5411},
Issue_Date = {May 2004},
Journal = {Journal of the ACM (J. ACM)},
Keywords = {Simplex method, complexity, perturbation, smoothed analysis},
Number = {3},
Numpages = {79},
Pages = {385--463},
Publisher = {ACM},
Title = {Smoothed Analysis of Algorithms: Why the Simplex Algorithm Usually Takes Polynomial Time},
Url = {http://doi.acm.org/10.1145/990308.990310},
Volume = {51},
Year = {2004},
Bdsk-Url-1 = {http://doi.acm.org/10.1145/990308.990310},
Bdsk-Url-2 = {http://dx.doi.org/10.1145/990308.990310}}
Downloads: 0
{"_id":"eadSj2hn3EdhR3p75","authorIDs":[],"author_short":["Spielman, D. A.","Teng, S."],"bibbaseid":"spielman-teng-smoothedanalysisofalgorithmswhythesimplexalgorithmusuallytakespolynomialtime-2004","bibdata":{"bibtype":"article","type":"article","acmid":"990310","address":"New York, NY, USA","author":[{"propositions":[],"lastnames":["Spielman"],"firstnames":["Daniel","A."],"suffixes":[]},{"propositions":[],"lastnames":["Teng"],"firstnames":["Shang-Hua"],"suffixes":[]}],"date-added":"2014-11-14 04:05:47 +0000","date-modified":"2014-11-14 04:06:31 +0000","doi":"10.1145/990308.990310","issn":"0004-5411","issue_date":"May 2004","journal":"Journal of the ACM (J. ACM)","keywords":"Simplex method, complexity, perturbation, smoothed analysis","number":"3","numpages":"79","pages":"385–463","publisher":"ACM","title":"Smoothed Analysis of Algorithms: Why the Simplex Algorithm Usually Takes Polynomial Time","url":"http://doi.acm.org/10.1145/990308.990310","volume":"51","year":"2004","bdsk-url-1":"http://doi.acm.org/10.1145/990308.990310","bdsk-url-2":"http://dx.doi.org/10.1145/990308.990310","bibtex":"@article{ST04,\n\tAcmid = {990310},\n\tAddress = {New York, NY, USA},\n\tAuthor = {Spielman, Daniel A. and Teng, Shang-Hua},\n\tDate-Added = {2014-11-14 04:05:47 +0000},\n\tDate-Modified = {2014-11-14 04:06:31 +0000},\n\tDoi = {10.1145/990308.990310},\n\tIssn = {0004-5411},\n\tIssue_Date = {May 2004},\n\tJournal = {Journal of the ACM (J. ACM)},\n\tKeywords = {Simplex method, complexity, perturbation, smoothed analysis},\n\tNumber = {3},\n\tNumpages = {79},\n\tPages = {385--463},\n\tPublisher = {ACM},\n\tTitle = {Smoothed Analysis of Algorithms: Why the Simplex Algorithm Usually Takes Polynomial Time},\n\tUrl = {http://doi.acm.org/10.1145/990308.990310},\n\tVolume = {51},\n\tYear = {2004},\n\tBdsk-Url-1 = {http://doi.acm.org/10.1145/990308.990310},\n\tBdsk-Url-2 = {http://dx.doi.org/10.1145/990308.990310}}\n\n","author_short":["Spielman, D. A.","Teng, S."],"key":"ST04","id":"ST04","bibbaseid":"spielman-teng-smoothedanalysisofalgorithmswhythesimplexalgorithmusuallytakespolynomialtime-2004","role":"author","urls":{"Paper":"http://doi.acm.org/10.1145/990308.990310"},"keyword":["Simplex method","complexity","perturbation","smoothed analysis"],"metadata":{"authorlinks":{}},"downloads":0},"bibtype":"article","biburl":"https://www.dropbox.com/s/jyw9acfkdge58zm/randomizedpolicyiteration.bib?dl=1","creationDate":"2014-11-14T04:29:26.928Z","downloads":0,"keywords":["simplex method","complexity","perturbation","smoothed analysis"],"search_terms":["smoothed","analysis","algorithms","simplex","algorithm","usually","takes","polynomial","time","spielman","teng"],"title":"Smoothed Analysis of Algorithms: Why the Simplex Algorithm Usually Takes Polynomial Time","year":2004,"dataSources":["mTaoW4bBjYJ2bpaP6"]}