






















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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。