Professor, University of Waterloo
[ Backtracking Algorithms
| Modeling in Constraint Programming
| Constraint Propagation ]
[ Local and Global Consistency in CSPs
| Planning, Sequencing, and Scheduling ]
[ Temporal Reasoning
| Plan Recognition and
Cooperative Response Generation ]
[ Theses
| Surveys
| Edited Books ]
| Backtracking Algorithms | ||
|---|---|---|
| Abstract |
Wei Li, Pascal Poupart, and Peter van Beek.
Exploiting causal independence using weighted model counting.
Proceedings of the 23rd AAAI Conference on
Artificial Intelligence,
Chicago, Ill., 337-343, July, 2008. |
|
| Abstract |
Huayue Wu and Peter van Beek.
On portfolios for backtracking search in the presence of deadlines.
Proceedings of the 19th IEEE International
Conference on Tools with Artificial Intelligence,
Patras, Greece, 231-238, October, 2007.
A longer
version appears in the
International J. of AI Tools,
(PDF),
17:835-855, 2008. |
|
| Abstract |
Huayue Wu and Peter van Beek.
On universal restart strategies for backtracking search.
Proceedings of the 13th International Conference on
Principles and Practice of Constraint Programming,
Providence, RI, 681-695, September, 2007. |
|
| Abstract | Wei Li, Peter van Beek, and Pascal Poupart. Performing incremental Bayesian inference by dynamic model counting. Proceedings of the 21st National Conference on Artificial Intelligence, Boston, Mass., 1173-1179, July, 2006. | |
| Abstract |
Wei Li and Peter van Beek.
Guiding real-world SAT solving with dynamic hypergraph
separator decomposition.
Proceedings of the Sixteenth IEEE International Conference
on Tools with Artificial Intelligence,
Boca Raton, Florida, 542-548, November, 2004. |
|
| Abstract |
Xinguang Chen and Peter van Beek.
Conflict-directed backjumping revisited.
Journal of Artificial Intelligence Research,
14:53-81, 2001. |
|
| Abstract |
Grzegorz Kondrak and Peter van Beek.
A theoretical evaluation of selected backtracking algorithms.
Artificial Intelligence,
89:365-387, 1997.
A preliminary version of the paper appears in
Proceedings of the Fourteenth International Joint Conference
on Artificial Intelligence,
Montreal, Quebec, 541-547, August, 1995. |
|
| Modeling in Constraint Programming | ||
|---|---|---|
| Abstract |
Tyrel Russell and Peter van Beek.
Lessons Learned from Modelling the NHL Playoff
Qualification Problem.
Proceedings of the Eighth International Workshop on
Constraint Modellig and Reformulation (ModRef'09),
Lisbon, Portugal, September, 2009. |
|
| Abstract |
Fahiem Bacchus, Xinguang Chen, Peter van Beek, and Toby Walsh.
Binary vs. non-binary constraints.
Artificial Intelligence,
140:1-37, 2002. |
|
| Abstract |
Adam Beacham, Xinguang Chen, Jonathan Sillito, and Peter van Beek.
Constraint programming lessons learned from crossword puzzles.
Proceedings of the 14th Canadian Conference on
Artificial Intelligence,
Ottawa, Ontario, 78-87, June, 2001. |
|
| Abstract |
Fahiem Bacchus and Peter van Beek.
On the conversion between non-binary and binary
constraint satisfaction problems.
Proceedings of the 15th National Conference on
Artificial Intelligence,
Madison, Wisconsin, 311-318, July, 1998. |
|
| Constraint Propagation | ||
|---|---|---|
| Abstract |
Lars Hellsten, Gilles Pesant, and Peter van Beek.
A domain consistency algorithm for the stretch constraint.
Proceedings of the 10th International Conference on
Principles and Practice of Constraint Programming,
Toronto, Ontario, 290-304, September, 2004. |
|
| Abstract |
Claude-Guy Quimper, Alejandro Lopez-Ortiz, Peter van Beek, and
Alexander Golynski.
Improved algorithms for the global cardinality constraint.
Proceedings of the 10th International Conference on
Principles and Practice of Constraint Programming,
Toronto, Ontario, 542-556, September, 2004. |
|
| Abstract |
Claude-Guy Quimper, Peter van Beek, Alejandro Lopez-Ortiz,
Alexander Golynski, and Sayyed Bashir Sadjad.
An efficient bounds consistency algorithm for the
global cardinality constraint.
Proceedings of the 9th International Conference on
Principles and Practice of Constraint Programming,
Kinsale, Ireland, 600-614, September, 2003.
A longer
technical report
version is available. |
|
| Abstract |
Alejandro Lopez-Ortiz, Claude-Guy Quimper, John Tromp, and
Peter van Beek.
A fast and simple algorithm for bounds consistency of the
alldifferent constraint.
Proceedings of the 18th International Joint Conference on
Artificial Intelligence,
Acapulco, Mexico, 245-250, August, 2003.
A longer
technical report
version is available. |
|
| Local and Global Consistency in CSPs | ||
|---|---|---|
| Abstract |
Peter van Beek and Rina Dechter.
Constraint tightness and looseness versus local and global consistency.
J. of the ACM,
44:549-566, 1997. |
|
| Abstract |
Rina Dechter and Peter van Beek.
Local and global relational consistency.
Theoretical Computer Science, 173:283-308, 1997.
A preliminary version of the paper appears in
Proceedings of the First International Conference on
Principles and Practices of Constraint Programming,
Cassis, France, 240-257, September, 1995. |
|
| Abstract |
Peter van Beek and Rina Dechter.
On the minimality and global consistency of row-convex constraint
networks.
J. ACM,
42:543-561, 1995. |
|
| Abstract |
Peter van Beek.
On the inherent level of local consistency in constraint networks.
Proceedings of the 12th National Conference on
Artificial Intelligence,
Seattle, Washington, 368-373, July, 1994. |
|
| Abstract |
Peter van Beek and Rina Dechter.
Constraint tightness versus global consistency.
Proceedings of the 4th International Conference on
Principles of Knowledge Representation and Reasoning,
Bonn, Germany, 572-582, May, 1994. |
|
| Abstract |
Peter van Beek.
On the minimality and decomposability of constraint networks.
Proceedings of the 10th National Conference on
Artificial Intelligence,
San Jose, California, 447-452, July, 1992. |
|
| Planning, Sequencing, and Scheduling | ||
|---|---|---|
| Abstract |
Tyrel Russell and Peter van Beek.
Determining the Number of Games Needed to Guarantee an NHL
Playoff Spot.
Proceedings of the Sixth International Conference on
Integration of AI and OR Techniques in Constraint
Programming for Combinatorial Optimization Problems
(CPAIOR 2009),
Pittsburgh, 233-247, May, 2009. |
|
| Abstract | Tyrel Russell, Abid M. Malik, Michael Chase, and Peter van Beek. Learning heuristics for the superblock instruction scheduling problem. IEEE Transactions on Knowledge and Data Engineering, 21(10):1489-1502, 2009. | |
| Abstract |
Abid M. Malik, Michael Chase, Tyrel Russell, and
Peter van Beek.
An Application of Constraint Programming to Superblock
Instruction Scheduling.
Proceedings of the 14th International Conference on
Principles and Practice of Constraint Programming,
Sydney, Australia, 97-111, September, 2008. |
|
| Abstract |
Tyrel Russell and Peter van Beek.
Mathematically Clinching a Playoff Spot in the NHL and the
Effect of Scoring Systems.
Proceedings of the 21st Canadian Conference on
Artificial Intelligence,
Windsor, Ontario, 234-245, May, 2008. |
|
| Abstract | Abid M. Malik, Tyrel Russell, Michael Chase, and Peter van Beek. Learning heuristics for basic block instruction scheduling. J. of Heuristics, 14(6):549-569, 2008. A preliminary version of the paper appears in Proceedings of the 15th CASCON, Toronto, Ontario, October, 2005. | |
| Abstract |
Abid M. Malik, Tyrel Russell, Michael Chase, and Peter van Beek.
Optimal superblock instruction scheduling for multiple-issue
processors using constraint programming.
Technical Report CS-2006-37,
School of Computer Science, University of Waterloo, 2006. |
|
| Abstract |
Abid M. Malik, Jim McInnes, and Peter van Beek.
Optimal basic block instruction scheduling for multiple-issue
processors using constraint programming.
Proceedings of the 18th IEEE International Conference
on Tools with Artificial Intelligence,
Washington, DC, 279-287, November, 2006.
A longer
version appears in the
International J. of AI Tools,
(PDF),
17:37-54, 2008. |
|
| Abstract |
Peter van Beek and Kent Wilken.
Fast optimal instruction scheduling for single-issue
processors with arbitrary latencies.
Proceedings of the Seventh International Conference on
Principles and Practice of Constraint Programming,
Paphos, Cyprus, 625-639, November, 2001. |
|
| Abstract |
Michael E. Bergen, Peter van Beek, and Tom Carchrae.
Constraint-based vehicle assembly line sequencing.
Proceedings of the 14th Canadian Conference on
Artificial Intelligence,
Ottawa, Ontario, 88-99, June, 2001. |
|
| Abstract |
Peter van Beek and Xinguang Chen.
CPlan: A constraint programming approach to planning.
Proceedings of the 16th National Conference on
Artificial Intelligence,
Orlando, Florida, 585-590, July, 1999. |
|
| Abstract |
Fulu Li, Ioanis Nikolaidis, Peter van Beek.
On the design of efficient video-on-demand broadcast schedules.
Proceedings of the Seventh International Symposium on
Modeling, Analysis, and Simulation of Computer and
Telecommunication Systems,
College Park, Maryland, 262-269, October, 1999. |
|
| Abstract |
Don Banks, Peter van Beek, and Amnon Meisels.
A heuristic incremental modeling approach to course timetabling.
Proceedings of the Twelfth Canadian Conference on
Artificial Intelligence,
Vancouver, British Columbia, 16-29, June, 1998. |
|
| Temporal Reasoning | ||
|---|---|---|
| Abstract |
Peter van Beek and Dennis W. Manchak.
The design and experimental analysis of algorithms for temporal
reasoning.
Journal of Artificial Intelligence Research
4:1-18, 1996. |
|
| Abstract |
Peter van Beek.
Reasoning about qualitative temporal information.
Artificial Intelligence
58:297-326, 1992.
Preliminary versions of the paper appear in
Proceedings of the 8th National Conference on
Artificial Intelligence,
Boston, Massachusetts, 728-734, July, 1990;
and in
Recent Advances in Qualitative Physics,
Boi Faltings and Peter Struss (eds.),
The MIT Press, 211-227, 1992. |
|
| Abstract |
Peter van Beek.
Temporal query processing with indefinite information.
Artificial Intelligence in Medicine
3:325-339, 1991. |
|
| Abstract |
Peter van Beek and Robin Cohen.
Exact and approximate reasoning about temporal relations.
Computational Intelligence
6:132-144, 1990. |
|
| Abstract |
Marc Vilain, Henry Kautz, and Peter van Beek.
Constraint propagation algorithms for temporal reasoning:
A revised report.
In Readings in Qualitative Reasoning about Physical Systems,
Daniel S. Weld and Johan de Kleer (eds.),
Morgan-Kaufman, 373-381, 1989. |
|
| Abstract |
Peter van Beek.
Approximation algorithms for temporal reasoning.
Proceedings of the 11th International Joint Conference on
Artificial Intelligence,
Detroit, Michigan, 1291-1296, August, 1989. |
|
| Plan Recognition | ||
|---|---|---|
| Abstract |
Peter van Beek.
An investigation of probabilistic interpretations of
heuristics in plan recognition.
Proceedings of the Fifth International Conference on
User Modeling,
Kailua-Kona, Hawaii, 113-120, January, 1996. |
|
| Abstract |
Robin Cohen, Ken Schmidt, and Peter van Beek.
A framework for soliciting clarification from users during
plan recognition.
Proceedings of the Fourth International Conference on
User Modeling,
Hyannis, Massachusetts, 11-17, August, 1994. |
|
| Abstract |
Peter van Beek, Robin Cohen, and Ken Schmidt.
From plan critiquing to clarification dialogue for
cooperative response generation.
Computational Intelligence,
9:132-154, 1993. |
|
| Abstract |
Peter van Beek and Robin Cohen.
Resolving plan ambiguity for cooperative response generation.
Proceedings of the Twelfth International Joint Conference
on Artificial Intelligence,
Sydney, Australia, 938-944, August, 1991. |
|
|
Robin Cohen, Fei Song, Bruce Spencer, and Peter van Beek.
Exploiting temporal and novel information from the user in
plan recognition.
User-Modeling and User-Adapted Interaction,
1:125-148, 1991. |
||
|
Peter van Beek.
A model for generating better explanations.
Proceedings of the 25th Conference of the Association
for Computational Linguistics,
Stanford, California, 215-220, July, 1987. |
||
|
Peter van Beek and Robin Cohen.
Towards user-specific explanations from expert systems.
Proceedings of the Sixth Canadian Conference on Artificial
Intelligence,
Montreal, Quebec, 194-198, May, 1986. |
||
| Theses | ||
|---|---|---|
| Abstract |
Zijie Li.
Backdoors in Satisfiability Problems.
MMath thesis,
University of Waterloo, School of Computer Science,
2009. |
|
| Abstract |
Abid Malik.
Constraint Programming Techniques for Optimal
Instruction Scheduling.
PhD thesis,
University of Waterloo, School of Computer Science,
2008. |
|
| Abstract |
Michael Chase.
On the Near-Optimality of List Scheduling Heuristics for
Local and Global Instruction Scheduling.
MMath thesis,
University of Waterloo, School of Computer Science,
2006. |
|
| Abstract |
Tyrel Russell.
Learning Instruction Scheduling Heuristics from Optimal Data.
MMath thesis,
University of Waterloo, School of Computer Science,
2006. |
|
| Abstract |
Huayue Wu.
Randomization and Restart Strategies.
MMath thesis,
University of Waterloo, School of Computer Science,
2006. |
|
| Abstract |
Lars Hellsten.
Consistency Propagation for Stretch Constraints.
MMath thesis,
University of Waterloo, School of Computer Science,
2004. |
|
| Abstract |
Jonathan Sillito.
Improvements to and estimating the cost of backtracking
algorithms for constraint satisfaction problems.
MSc thesis,
University of Alberta, Department of Computing Science,
2000. |
|
| Abstract |
Michael Bergen.
Constraint-based assembly line sequencing.
MSc thesis,
University of Alberta, Department of Computing Science,
2000. |
|
| Abstract |
Xinguang Chen.
A theoretical comparison of selected CSP solving
and modeling techniques.
PhD thesis,
University of Alberta, Department of Computing Science,
2000. |
|
|
Donald Banks.
A constraint satisfaction approach to timetabling.
MSc thesis,
University of Alberta, Department of Computing Science,
1996. |
||
| Abstract |
Grzegorz Kondrak.
A theoretical evaluation of selected backtracking algorithms.
MSc thesis,
University of Alberta, Department of Computing Science,
1994. |
|
|
Kenneth J. Schmidt.
Clarification dialogues for plan recognition in advice-giving systems.
MSc thesis,
University of Alberta, Department of Computing Science,
1994. |
||
|
Alan D. Sharpe.
An adaptive approach for acquiring missing knowledge.
MSc thesis,
University of Alberta, Department of Computing Science,
1993. |
||
| Abstract |
Peter van Beek.
Exact and approximate reasoning about qualitative temporal relations.
PhD thesis,
University of Waterloo, Department of Computer Science,
1990. |
|
| Surveys | ||
|---|---|---|
| Abstract |
Francesca Rossi, Peter van Beek, and Toby Walsh.
Constraint Programming.
Chapter 4 in
Handbook of Knowledge Representation,
Handbook of Knowledge Representation,
B. Porter, V. Lifschitz, F. van Harmelen (eds.),
Elsevier, 2007. |
|
| Abstract |
Peter van Beek.
Backtracking search algorithms.
Chapter 4 in
Handbook of Constraint Programming,
F. Rossi, P. van Beek, T. Walsh (eds.),
Elsevier, 2006. |
|
| Edited Books | ||
|---|---|---|
|
Peter van Beek (ed.).
Proceedings of the 11th International Conference on
Principles and Practice of Constraint Programming,
Sitges, Spain, 2005. Appears as:
Lecture Notes in Computer Science 3709,
Springer-Verlag. |
||
| Francesca Rossi, Peter van Beek, and Toby Walsh (eds.), Handbook of Constraint Programming, Handbook of Constraint Programming, Elsevier, 2006. | ||