Scholarlink

<p>The quality of enumeration algorithms is often measured by their delay, that is, the maximum time spent between the output of two distinct solutions. If the goal is to enumerate <i>t</i> distinct solutions for any given <i>t</i>, another relevant measure is the maximum time needed to output <i>t</i> solutions divided by <i>t</i>, a notion we call the <i>amortized delay</i> of the algorithm, since it can be seen as the amortized complexity of enumerating <i>t</i> elements of the set.</p><p>In this paper, we study the relationship between these two notions of delay. We present several schemes that transform an algorithm with polynomial amortized delay, accessible only as a black box, into an algorithm with polynomial delay. We complement these results with several lower bounds and impossibility theorems in the black-box model.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

From amortized to worst case delay in enumeration algorithms

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年7月20日

查看全文
  • Florent Capelli,
  • Yann Strozecki

摘要

The quality of enumeration algorithms is often measured by their delay, that is, the maximum time spent between the output of two distinct solutions. If the goal is to enumerate t distinct solutions for any given t, another relevant measure is the maximum 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 enumerating t elements of the set.

In this paper, we study the relationship between these two notions of delay. We present several schemes that transform an algorithm with polynomial amortized delay, accessible only as a black box, into an algorithm with polynomial delay. We complement these results with several lower bounds and impossibility theorems in the black-box model.