From Amortized to Worst Case Delay in Enumeration Algorithms
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2021
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909302661316608 |
|---|---|
| author | Capelli, Florent Strozecki, Yann |
| author_facet | Capelli, Florent Strozecki, Yann |
| contents | The quality of enumeration algorithms is often measured by their delay, that is, the maximal time spent between the output of two distinct solutions. If the goal is to enumerate $t$ distinct solutions for any given $t$, then another relevant measure is the maximal time needed to output $t$ solutions divided by $t$, a notion we call the amortized delay of the algorithm, since it can be seen as the amortized complexity of the problem of enumerating $t$ elements in the set. In this paper, we study the relation between these two notions of delay, showing different schemes allowing one to transform an algorithm with polynomial amortized delay for which one has a blackbox access into an algorithm with polynomial delay. We complement our results by providing several lower bounds and impossibility theorems in the blackbox model. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2108_10208 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | From Amortized to Worst Case Delay in Enumeration Algorithms Capelli, Florent Strozecki, Yann Computational Complexity Data Structures and Algorithms The quality of enumeration algorithms is often measured by their delay, that is, the maximal time spent between the output of two distinct solutions. If the goal is to enumerate $t$ distinct solutions for any given $t$, then another relevant measure is the maximal time needed to output $t$ solutions divided by $t$, a notion we call the amortized delay of the algorithm, since it can be seen as the amortized complexity of the problem of enumerating $t$ elements in the set. In this paper, we study the relation between these two notions of delay, showing different schemes allowing one to transform an algorithm with polynomial amortized delay for which one has a blackbox access into an algorithm with polynomial delay. We complement our results by providing several lower bounds and impossibility theorems in the blackbox model. |
| title | From Amortized to Worst Case Delay in Enumeration Algorithms |
| topic | Computational Complexity Data Structures and Algorithms |
| url | https://arxiv.org/abs/2108.10208 |