Modular smoothed analysis

Show simple item record

dc.contributor.author Schellekens, Michel P.
dc.contributor.author Hennessy, Aoife
dc.contributor.author Shi, Bichen
dc.date.accessioned 2014-02-05T09:57:18Z
dc.date.available 2014-02-05T09:57:18Z
dc.date.issued 2014
dc.identifier.citation SCHELLEKENS, M. P., HENNESSY, A. & SHI, B. 2014. Modular smoothed analysis. Submitted to Discrete Mathematics. [Preprint] en
dc.identifier.issn 0012-365X
dc.identifier.issn 1872-681X
dc.identifier.uri http://hdl.handle.net/10468/1368
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. 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.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 Smoothed analysis en
dc.subject MOQA en
dc.subject Recursive partial permutation model en
dc.title Modular smoothed analysis 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 Peer reviewed en
dc.identifier.journaltitle Discrete Mathematics en
dc.internal.IRISemailaddress m.schellekens@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