### Citation

(PDF)
Peter van Beek.
Approximation algorithms for temporal reasoning.
*Proceedings of the 11th International Joint Conference on
Artificial Intelligence,*
Detroit, Michigan, 1291-1296, August, 1989.

### Abstract

We consider a representation for temporal relations between intervals
introduced by James Allen, and its associated computational or
reasoning problem: given possibly indefinite knowledge of the relations
between some intervals, how do we compute the strongest possible
assertions about the relations between some or all intervals.
Determining exact solutions to this problem has been shown to be
(almost assuredly) intractable. Allen gives an approximation algorithm
based on constraint propagation. We give new approximation algorithms,
examine their effectiveness, and determine under what conditions the
algorithms are exact.

**Return to Publications**