Modular smoothed analysis
| dc.contributor.author | Schellekens, Michel P. | |
| dc.contributor.author | Hennessy, Aoife | |
| dc.contributor.author | Shi, Bichen | |
| dc.contributor.funder | Science Foundation Ireland | en |
| dc.date.accessioned | 2014-02-05T09:57:18Z | |
| dc.date.available | 2014-02-05T09:57:18Z | |
| dc.date.issued | 2014 | |
| 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.description.status | Peer reviewed | en |
| dc.description.version | Submitted Version | en |
| dc.format.mimetype | application/pdf | en |
| 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.journaltitle | Discrete Mathematics | en |
| dc.identifier.uri | https://hdl.handle.net/10468/1368 | |
| 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 |