Modular smoothed analysis

dc.contributor.authorSchellekens, Michel P.
dc.contributor.authorHennessy, Aoife
dc.contributor.authorShi, Bichen
dc.contributor.funderScience Foundation Irelanden
dc.date.accessioned2014-02-05T09:57:18Z
dc.date.available2014-02-05T09:57:18Z
dc.date.issued2014
dc.description.abstractSpielman’s smoothed complexity - a hybrid between worst and average case complexity measures - relies on perturbations of input instances to determine where average-case behavior turns to worst-case. The paper proposes a method supporting modular smoothed analysis. The method, involving a novel permutation model, is developed for the discrete case, focusing on randomness preserving algorithms. This approach simplifies the smoothed analysis and achieves greater precession in the expression of the smoothed complexity, where a recurrence equation is obtained as opposed to bounds. Moreover, the approach addresses, in this context, the formation of input instances–an open problem in smoothed complexity. To illustrate the method, we determine the modular smoothed complexity of Quicksort.en
dc.description.sponsorshipScience Foundation Ireland (SFI 07/IN.1/I977)en
dc.description.statusPeer revieweden
dc.description.versionSubmitted Versionen
dc.format.mimetypeapplication/pdfen
dc.identifier.citationSCHELLEKENS, M. P., HENNESSY, A. & SHI, B. 2014. Modular smoothed analysis. Submitted to Discrete Mathematics. [Preprint]en
dc.identifier.issn0012-365X
dc.identifier.issn1872-681X
dc.identifier.journaltitleDiscrete Mathematicsen
dc.identifier.urihttps://hdl.handle.net/10468/1368
dc.language.isoenen
dc.publisherElsevieren
dc.relation.urihttp://www.sciencedirect.com/science/journal/0012365X
dc.subjectSmoothed analysisen
dc.subjectMOQAen
dc.subjectRecursive partial permutation modelen
dc.titleModular smoothed analysisen
dc.typeArticle (preprint)en
Files
Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
MPS_ModularSV2014.pdf
Size:
563.04 KB
Format:
Adobe Portable Document Format
Description:
Submitted Version
License bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
license.txt
Size:
2.71 KB
Format:
Item-specific license agreed upon to submission
Description: