b'@inproceedings{Beier2003a,'b"\nTITLE = {Smoothed Analysis of Three Combinatorial Problems},\nAUTHOR = {Banderier, Cyril and Beier, Rene and Mehlhorn, Kurt},\nEDITOR = {Rovan, Branislav and Vojt{\\'a}{\\v s}, Peter},\nLANGUAGE = {eng},\nISBN = {3-540-40671-9},\nLOCALID = {Local-ID: C1256428004B93B8-09CF39E77E5072D5C1256E140059E6C7-Beier2003a},\nPUBLISHER = {Springer},\nYEAR = {2003},\nDATE = {2003},\nABSTRACT = {Smoothed analysis combines elements over worst-case and average case analysis. For an instance $x$, the smoothed complexity is the average complexity of an instance obtained from $x$ by a perturbation. The smoothed complexity of a problem is the worst smoothed complexity of any instance. Spielman and Teng introduced this notion for continuous problems. We apply the concept to combinatorial problems and study the smoothed complexity of three classical discrete problems: quicksort, left-to-right maxima counting, and shortest paths.},\nBOOKTITLE = {Mathematical foundations of computer science 2003 : 28th International Symposium, MFCS 2003},\nPAGES = {198--207},\nSERIES = {Lecture Notes in Computer Science},\nVOLUME = {2747},\nADDRESS = {Bratislava, Slovak Republic},\n}\n"