15th IEEE International Conference on Tools with Artificial Intelligence (ICTAI'03) Implicit Random Constraint Satisfaction Problems Sacramento, California, USA November 03-November 05 ISBN: 0-7695-2038-3
Random CSPs (Constraint Satisfaction Problems) provide interesting benchmarks for experimental evaluation of algorithms. From a theoretical point of view, a lot of recent works have contributed to guarantee the existence of a so-called phase transition and, consequently, of hard and large problem instances. From a practical point of view, due to exponential space complexity, a vast majority of experiments based on random CSPs concerns binary problems. In this paper, we introduce a model of implicit random CSPs, i.e., of random CSPs where constraints are not given in extension but defined by a predicate. This new model involves an easy implementation, no space requirement and the possibility to perform experiments with large arity constraints.
Citation:
Christophe Lecoutre, Frédéric Boussemart, Fred Hemery, "Implicit Random Constraint Satisfaction Problems," ictai, pp.482, 15th IEEE International Conference on Tools with Artificial Intelligence (ICTAI'03), 2003 Usage of this product signifies your acceptance of the Terms of Use. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||