Approximation Algorithms for Temporal Reasoning
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 giv e new approximation algorithms, examine their effectiveness, and determine under what conditions the algorithms are exact.
Cite
Text
van Beek. "Approximation Algorithms for Temporal Reasoning." International Joint Conference on Artificial Intelligence, 1989.Markdown
[van Beek. "Approximation Algorithms for Temporal Reasoning." International Joint Conference on Artificial Intelligence, 1989.](https://mlanthology.org/ijcai/1989/vanbeek1989ijcai-approximation/)BibTeX
@inproceedings{vanbeek1989ijcai-approximation,
title = {{Approximation Algorithms for Temporal Reasoning}},
author = {van Beek, Peter},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {1989},
pages = {1291-1296},
url = {https://mlanthology.org/ijcai/1989/vanbeek1989ijcai-approximation/}
}