Modular smoothed analysis of median-of-three Quicksort

Show simple item record

dc.contributor.author Hennessy, Aoife
dc.contributor.author Schellekens, Michel P.
dc.date.accessioned 2014-02-05T09:48:26Z
dc.date.available 2014-02-05T09:48:26Z
dc.date.issued 2014
dc.identifier.citation HENNESSY, A. & SCHELLEKENS, M. P. 2014. Modular smoothed analysis of median-of-three Quicksort. Submitted to: Discrete Mathematics. [Preprint] en
dc.identifier.issn 1872-681X
dc.identifier.issn 0012-365X
dc.identifier.uri http://hdl.handle.net/10468/1367
dc.description.abstract Spielman’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.sponsorship Science Foundation Ireland (SFI 07/IN.1/I977) en
dc.format.mimetype application/pdf en
dc.language.iso en en
dc.publisher Elsevier en
dc.relation.uri http://www.sciencedirect.com/science/journal/0012365X
dc.subject Modular smoothed analysis en
dc.subject MOQA en
dc.subject Median-of-three Quicksort en
dc.title Modular smoothed analysis of median-of-three Quicksort en
dc.type Article (preprint) en
dc.internal.availability Full text available en
dc.description.version Submitted Version en
dc.contributor.funder Science Foundation Ireland en
dc.description.status Not peer reviewed en
dc.identifier.journaltitle Discrete Mathematics en
dc.internal.copyrightchecked !!CORA!! Elsevier article posting policies from their website. http://www.elsevier.com/about/open-access/open-access-policies/article-posting-policy In general, Elsevier is permissive with respect to authors and electronic preprints. If an electronic preprint of an article is placed on a public server prior to its submission to an Elsevier journal or where a paper was originally authored as a thesis or dissertation, this is not generally viewed by Elsevier as “prior publication” and therefore Elsevier will not require authors to remove electronic preprints of an article from public servers should the article be accepted for publication in an Elsevier journal en
dc.internal.copyrightchecked !!CORA!! Elsevier article posting policies from their website. http://www.elsevier.com/about/open-access/open-access-policies/article-posting-policy In general, Elsevier is permissive with respect to authors and electronic preprints. If an electronic preprint of an article is placed on a public server prior to its submission to an Elsevier journal or where a paper was originally authored as a thesis or dissertation, this is not generally viewed by Elsevier as “prior publication” and therefore Elsevier will not require authors to remove electronic preprints of an article from public servers should the article be accepted for publication in an Elsevier journal
dc.internal.IRISemailaddress a.hennessy@cs.ucc.ie en


Files in this item

This item appears in the following Collection(s)

Show simple item record

This website uses cookies. By using this website, you consent to the use of cookies in accordance with the UCC Privacy and Cookies Statement. For more information about cookies and how you can disable them, visit our Privacy and Cookies statement