Polynomial delay

In the analysis of algorithms, an algorithm for listing a large or infinite collection of structures is said to have polynomial delay if the time between the output of any one structure and the next is bounded by a polynomial function of the input size, in the worst case.[1]

Polynomial delay implies that the total time used by an algorithm will be polynomial per output item, but is a stronger requirement. This is a desirable property, because it means that any consumer of the stream of outputs will not have to wait idle for a long time from one output to the next. In particular, an algorithm with polynomial delay cannot have a startup phase that takes exponential time before it produces a single output, unlike some algorithms that take polynomial time per output item.[2] Additionally, unlike bounds on the total time, it is a suitable form of analysis even for algorithms that produce an infinite sequence of outputs.

The notion of polynomial delay was first introduced by Johnson, Yannakakis & Papadimitriou (1988).

References

  1. ↑ Goldberg, Leslie Ann (1993), Efficient Algorithms for Listing Combinatorial Structures, Distinguished Dissertations in Computer Science, 5, Cambridge University Press, p. vii, ISBN 9780521117883.
  2. ↑ Johnson, David S.; Yannakakis, Mihalis; Papadimitriou, Christos H. (1988), "On generating all maximal independent sets", Information Processing Letters, 27 (3): 119–123, doi:10.1016/0020-0190(88)90065-8, MR 933271.
This article is issued from Wikipedia - version of the 9/18/2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.