Modular smoothed analysis of median-of-three Quicksort

Simple item page
dc.contributor.authorHennessy, Aoife
dc.contributor.authorSchellekens, Michel P.
dc.contributor.funderScience Foundation Irelanden
dc.date.accessioned2014-02-05T09:48:26Z
dc.date.available2014-02-05T09:48:26Z
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. 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. In [23], we proposed a method supporting modular smoothed analysis and illustrated the method by determining the modular smoothed complexity of Quicksort. Here, we use the modular approach to calculate the median of three variant and compare these results with those in [23].en
dc.description.sponsorshipScience Foundation Ireland (SFI 07/IN.1/I977)en
dc.description.statusNot peer revieweden
dc.description.versionSubmitted Versionen
dc.format.mimetypeapplication/pdfen
dc.identifier.citationHENNESSY, A. & SCHELLEKENS, M. P. 2014. Modular smoothed analysis of median-of-three Quicksort. Submitted to: Discrete Mathematics. [Preprint]en
dc.identifier.issn1872-681X
dc.identifier.issn0012-365X
dc.identifier.journaltitleDiscrete Mathematicsen
dc.identifier.urihttps://hdl.handle.net/10468/1367
dc.language.isoenen
dc.publisherElsevieren
dc.relation.urihttp://www.sciencedirect.com/science/journal/0012365X
dc.subjectModular smoothed analysisen
dc.subjectMOQAen
dc.subjectMedian-of-three Quicksorten
dc.titleModular smoothed analysis of median-of-three Quicksorten
dc.typeArticle (preprint)en
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
AH_ModularSV2014.pdf
Size:
243.09 KB
Format:
Adobe Portable Document Format
Description:
Submitted Version
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
2.71 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
CEOL: Centre for Efficiency-Oriented Languages - Journal Articles
Computer Science - Journal Articles