there are several instances where MAC is outperformed (e.g. the graph RLFAPs and most quasigroup problems). Of course, there are still instances where MAC
remains considerably faster despite the improvements.

| Problem class         | ACrm lmaxRPCrm lmaxRPC3rm lmaxRPCrm + H lmaxRPC3rm + H   |        |       |        |       |       |
|-----------------------|----------------------------------------------------------|--------|-------|--------|-------|-------|
| RLFAP                 | t                                                        | 242.8  | 556.7 | 199.3  | 416.3 | 157.3 |
| (scen,graph)          | cc 233M                                                  | 2,306M | 663M  | 1,580M | 487M  |       |
| Random                | t                                                        | 8.4    | 28.0  | 14.8   | 28.5  | 17.1  |
| (modelB,forced)       | cc                                                       | 14M    | 161M  | 60M    | 137M  | 51M   |
| Geometric             | t                                                        | 21.5   | 72.2  | 37.2   | 57.6  | 32.1  |
| cc                    | 39M                                                      | 418M   | 179M  | 297M   | 126M  |       |
| Quasigroup            | t                                                        | 147.0  | 162.5 | 94.9   | 128.9 | 89.6  |
| (qcp,qwh,bqwh)        | cc                                                       | 59M    | 562M  | 68M    | 333M  | 40M   |
| QueensKnights,        | t                                                        | 90.2   | 505.2 | 180.3  | 496.4 | 198.1 |
| Queens,QueenAttack cc | 74M                                                      | 1,865M | 570M  | 1,891M | 654M  |       |
| driver,blackHole      | t                                                        | 3.2    | 17.1  | 9.1    | 11.9  | 7.0   |
| haystacks,job-shop    | cc                                                       | 1.8M   | 55M   | 6.4M   | 36.7M | 5.1M  |

Table 4 summarizes results from the application of lmaxRPC during search.

We give average results for all the tested instances, grouped into specific problem classes. As can be seen, our best method improves on the existing best one considerably, making lmaxRPC outperform MAC on the RFLAP and quasigroup problem classes. Overall, our results demonstrate that the efficient application of a maxRPC approximation throughout search can give an algorithm that is quite competitive with MAC on many binary CSPs. This confirms the conjecture of [6] about the potential of maxRPC as an alternative to AC. In addition, our results, along with ones in [10], show that approximating strong and complex local consistencies can be very beneficial.

## 6 Conclusion

We presented maxRPC3 and maxRPC3rm, two new algorithms for maxRPC, and their light versions that approximate maxRPC. These algorithms build on and improve existing maxRPC algorithms, achieving the elimination of many redundant constraint checks. We also investigated heuristics that can be used to order certain operations within maxRPC algorithms. Experimental results from various problem classes demonstrate that our best method, lmaxRPC3rm, constantly outperforms existing algorithms, often by large margins. Significantly, the speed-ups obtained allow lmaxRPC3rm to compete with and outperform MAC on many problems. In the future we plan to adapt techniques for using residues from [9] to improve the