---
title: "Improved bounds on the complexity of kB-consistency"
authors:
  - "Lucas Bordeaux"
  - "Éric Monfroy"
  - "Frédéric Benhamou"
doi: ""
url: "https://ijcai.org/proceedings/2001/43"
pdf: "https://ijcai.org/proceedings/2001/0043.pdf"
venue: "Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence"
year: 2001
pages: "303-307"
track: ""
keywords:
---

# Improved bounds on the complexity of kB-consistency

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

*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