| Author | dc.contributor.author | Barbay, Jérémy | |
| Author | dc.contributor.author | Kenyon, Claire | es_CL |
| Admission date | dc.date.accessioned | 2009-07-09T16:10:54Z | |
| Available date | dc.date.available | 2009-07-09T16:10:54Z | |
| Publication date | dc.date.issued | 2008-03 | |
| Cita de ítem | dc.identifier.citation | ACM TRANSACTIONS ON ALGORITHMS. V,: 4, Issue: 1, Article N.: 4, MAR 2008. | en |
| Identifier | dc.identifier.issn | 1549-6325 | |
| Identifier | dc.identifier.uri | https://repositorio.uchile.cl/handle/2250/125028 | |
| Abstract | dc.description.abstract | The intersection of sorted arrays problem has applications in search engines such as Google.
Previous work has proposed and compared deterministic algorithms for this problem, in an adaptive
analysis based on the encoding size of a certificate of the result (cost analysis).We define the alternation
analysis, based on the nondeterministic complexity of an instance. In this analysis we prove that there
is a deterministic algorithm asymptotically performing as well as any randomized algorithm in the
comparison model.We define the redundancy analysis, based on a measure of the internal redundancy
of the instance. In this analysis we prove that any algorithm optimal in the redundancy analysis is
optimal in the alternation analysis, but that there is a randomized algorithm which performs strictly
better than any deterministic algorithm in the comparison | en |
| Lenguage | dc.language.iso | en | en |
| Publisher | dc.publisher | ASSOC COMPUTING MACHINERY | en |
| Keywords | dc.subject | F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems—Sorting and searching | en |
| Título | dc.title | Alternation and Redundancy Analysis of the Intersection Problem | en |
| Document type | dc.type | Artículo de revista | |
