Improved Bounds on the Complexity of kB-Consistency
Abstract
Abstract-consistencies form the class of strong consis-tencies used in interval constraint programming. We survey, prove, and give theoretical motivations to some technical improvements to a naive ¢¤£ consistency algorithm. Our contribution is twofold: on the one hand, we introduce an ¥ optimal-consistency algorithm whose time-complexity ¦¨§�©�������� of improves the known bound by a � factor is the number of constraints, � is the number of variables, and � is the maximal size of the intervals of the box). On the other hand, we prove that improved bounds on time complexity can effectively be reached for higher values of ¢. These results are obtained with very affordable overheads in terms of space complexity.
Cite
Text
Bordeaux et al. "Improved Bounds on the Complexity of kB-Consistency." International Joint Conference on Artificial Intelligence, 2001.Markdown
[Bordeaux et al. "Improved Bounds on the Complexity of kB-Consistency." International Joint Conference on Artificial Intelligence, 2001.](https://mlanthology.org/ijcai/2001/bordeaux2001ijcai-improved/)BibTeX
@inproceedings{bordeaux2001ijcai-improved,
title = {{Improved Bounds on the Complexity of kB-Consistency}},
author = {Bordeaux, Lucas and Monfroy, Éric and Benhamou, Frédéric},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2001},
pages = {303-308},
url = {https://mlanthology.org/ijcai/2001/bordeaux2001ijcai-improved/}
}