Loading...
Please wait, while we are loading the content...
Similar Documents
Generating satisfiable problem instances (2000)
| Content Provider | CiteSeerX |
|---|---|
| Author | Achlioptas, Dimitris Gomes, Carla Kautz, Henry Selman, Bart |
| Description | A major difficulty in evaluating incomplete local search style algorithms for constraint satisfaction problems is the need for a source of hard problem instances that are guaranteed to be satisfiable. A standard approach to evaluate incomplete search methods has been to use a general problem genera-tor and a complete search method to filter out the unsatisfi-able instances. Unfortunately, this approach cannot be used to create problem instances that are beyond the reach of com-plete search methods. So far, it has proven to be surprisingly difficult to develop a direct generator for satisfiable instances only. In this paper, we propose a generator that only out-puts satisfiable problem instances. We also show how one can finely control the hardness of the satisfiable instances by es-tablishing a connection between problem hardness and a new kind of phase transition phenomenon in the space of prob-lem instances. Finally, we use our problem distribution to show the easy-hard-easy pattern in search complexity for lo-cal search procedures, analogous to the previously reported pattern for complete search methods. |
| File Format | |
| Language | English |
| Publisher Date | 2000-01-01 |
| Publisher Institution | In AAAI/IAAI. 256–261 |
| Access Restriction | Open |
| Subject Keyword | General Problem Genera-tor Standard Approach Problem Hardness Incomplete Local Search Style Algorithm Prob-lem Instance Hard Problem Instance Complete Search Method Easy-hard-easy Pattern Problem Distribution Direct Generator Satisfiable Problem Instance Lo-cal Search Procedure Constraint Satisfaction Problem Phase Transition Phenomenon Unsatisfi-able Instance Search Complexity Incomplete Search Method Major Difficulty Approach Cannot Satisfiable Instance Problem Instance New Kind Com-plete Search Method |
| Content Type | Text |
| Resource Type | Article |
