How to Solve Interval Constraint Networks: The Definitive Answer - Probably
| Title | How to Solve Interval Constraint Networks: The Definitive Answer - Probably |
| Publication Type | Technical Report |
| Year of Publication | 1991 |
| Authors | Ladkin, P., & Reinefeld A. |
| Other Numbers | 693 |
| Abstract | We implemented and tested an algorithm for solving interval constraint problems which returned solutions in less than or equal to 0.5 seconds on the average, with the hardest problem taking less than or equal to 0.5 minutes on a RISC workstation. This is a surprising result considering the problem is known to be NP-complete. We conclude that our algorithm suffices for solving random interval constraint problems in practice.Other conclusions are that path-consistency is an excellent pruning technique for solution search, which becomes almost a linear selection of atomic labels; also that path-consistency by itself is an excellent consistency heuristic for networks with fewer than six or greater than 15 nodes. We tested the algorithm on over two million randomly generated interval networks of various sizes, hence our title. |
| URL | http://www.icsi.berkeley.edu/pubs/techreports/tr-91-063.pdf |
| Bibliographic Notes | ICSI Technical Report TR-91-063 |
| Abbreviated Authors | P. Ladkin and A. Reinefeld |
| ICSI Publication Type | Technical Report |