TY - JOUR

T1 - The expected value and the variance of the checks required by revision algorithms

AU - Dongen, van, M.R.C.

AU - Dieker, A.B.

AU - Sapozhnikov, A.

PY - 2008

Y1 - 2008

N2 - This paper presents the analysis of three revision algorithms for 2-variable Constraint Satisfaction Problems (CSPs). The revision algorithms under consideration are called L, L’, and L’’. For 2-variable CSPs L models an optimal arc consistency algorithm which exploits multi-directionality. However, L’ and L’’ do not exploit multi-directionality. For 2-variable CSPs L’ is equivalent to the arc consistency algorithm AC-3. The expected number and the variance of the checks are presented for L, L’, and L’’. Writing A _ B if the expected number of checks for A is less than for B, we have L _ L’ _ L’’. The results are parametrised over the probability p that a random check succeeds and probability q = 1-p that it fails. It is proved that the difference between the expected number of checks of any two algorithms is bounded by min(b, 1 + d ln(a)/ ln(1/q) e)/p. Using a variance analysis, it is proved that, as the domain sizes a and b become large, the number of checks which are required by the revision algorithms is sharply concentrated about their expected number of checks. Finally, our analysis allows us to find an upper bound of 2ed/p + (2e - n)d(d - 1)/2p for the expected time complexity of AC-3, where e is the number of constraints, n is the umber of variables, and d is the maximum domain size. These results are novel and encouraging. First they provide the first non-trivial upper bound on the expected time complexity of AC-3. Second, they demonstrate that on average there is a small margin separating L, L’, and L’’. Finally, they present the first results about the variance of the checks required by revision algorithms.

AB - This paper presents the analysis of three revision algorithms for 2-variable Constraint Satisfaction Problems (CSPs). The revision algorithms under consideration are called L, L’, and L’’. For 2-variable CSPs L models an optimal arc consistency algorithm which exploits multi-directionality. However, L’ and L’’ do not exploit multi-directionality. For 2-variable CSPs L’ is equivalent to the arc consistency algorithm AC-3. The expected number and the variance of the checks are presented for L, L’, and L’’. Writing A _ B if the expected number of checks for A is less than for B, we have L _ L’ _ L’’. The results are parametrised over the probability p that a random check succeeds and probability q = 1-p that it fails. It is proved that the difference between the expected number of checks of any two algorithms is bounded by min(b, 1 + d ln(a)/ ln(1/q) e)/p. Using a variance analysis, it is proved that, as the domain sizes a and b become large, the number of checks which are required by the revision algorithms is sharply concentrated about their expected number of checks. Finally, our analysis allows us to find an upper bound of 2ed/p + (2e - n)d(d - 1)/2p for the expected time complexity of AC-3, where e is the number of constraints, n is the umber of variables, and d is the maximum domain size. These results are novel and encouraging. First they provide the first non-trivial upper bound on the expected time complexity of AC-3. Second, they demonstrate that on average there is a small margin separating L, L’, and L’’. Finally, they present the first results about the variance of the checks required by revision algorithms.

M3 - Article

VL - 2

SP - 55

EP - 77

JO - Constraint Programming Letters

JF - Constraint Programming Letters

SN - 1932-0973

ER -