Improved bounds on the complexity of kB-consistency

Bordeaux, Lucas; Monfroy, Éric; Benhamou, Frédéric

Improved bounds on the complexity of kB-consistency

Lucas Bordeaux, Éric Monfroy, Frédéric Benhamou

Download BibTeX Cite

Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence. Pages 303-307.

Abstract

-consistencies form the class of strong consistencies 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

Lucas Bordeaux, Éric Monfroy, and Frédéric Benhamou. 2001. Improved bounds on the complexity of kB-consistency. In Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, IJCAI-01. IJCAI, 303–307. https://ijcai.org/proceedings/2001/43

@inproceedings{ijcai2001p43,
  title     = {Improved bounds on the complexity of kB-consistency},
  author    = {Bordeaux, Lucas and Monfroy, Éric and Benhamou, Frédéric},
  booktitle = {Proceedings of the Seventeenth International Joint Conference on
               Artificial Intelligence, {IJCAI-01}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  pages     = {303--307},
  year      = {2001},
  url       = {https://ijcai.org/proceedings/2001/43},
}

TY  - CPAPER
TI  - Improved bounds on the complexity of kB-consistency
AU  - Bordeaux, Lucas
AU  - Monfroy, Éric
AU  - Benhamou, Frédéric
T2  - Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, IJCAI-01
PB  - International Joint Conferences on Artificial Intelligence
PY  - 2001
SP  - 303
EP  - 307
UR  - https://ijcai.org/proceedings/2001/43
ER  -