Arrow Research search

Author name cluster

Barbara M. Smith

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

9 papers
2 author rows

Possible papers

9

IJCAI Conference 2005 Conference Paper

Value Ordering for Finding All Solutions

  • Barbara M. Smith
  • Paula

In finding all solutions to a constraint satisfaction problem, or proving that there are none, with a search algorithm that backtracks chronologically and forms k-way branches, the order in which the values are assigned is immaterial. However, we show that if the values of a variable are assigned instead via a sequence of binary choice points, and the removal of the value just tried from the domain of the variable is propagated before another value is selected, the value ordering can affect the search effort. We show that this depends on the problem constraints; for some types of constraints, we show that the savings in search effort can be significant, given a good value ordering.

PDF

TCS Journal 2001 Journal Article

Constructing an asymptotic phase transition in random binary constraint satisfaction problems

  • Barbara M. Smith

The standard models used to generate random binary constraint satisfaction problems are described. At the problem sizes studied experimentally, a phase transition is seen as the constraint tightness is varied. However, Achlioptas et al. Lecture Notes in computer science, Vol. 1330, 107–120 showed that if the problem size (number of variables) increases while the remaining parameters are kept constant, asymptotically almost all instances are unsatisfiable. In this paper, an alternative scheme for one of the standard models is proposed in which both the number of values in each variable's domain and the average degree of the constraint graph are increased with problem size. It is shown that with this scheme there is asymptotically a range of values of the constraint tightness in which instances are trivially satisfiable with probability at least 0. 5 and a range in which instances are almost all unsatisfiable; hence there is a crossover point at some value of the constraint tightness between these two ranges. This scheme is compared to a similar scheme due to Xu and Li.

Details DOI

AIJ Journal 1996 Journal Article

Locating the phase transition in binary constraint satisfaction problems

  • Barbara M. Smith
  • Martin E. Dyer

The phase transition in binary constraint satisfaction problems, i. e. the transition from a region in which almost all problems have many solutions to a region in which almost all problems have no solutions, as the constraints become tighter, is investigated by examining the behaviour of samples of randomly-generated problems. In contrast to theoretical work, which is concerned with the asymptotic behaviour of problems as the number of variables becomes larger, this paper is concerned with the location of the phase transition in finite problems. The accuracy of a prediction based on the expected number of solutions is discussed; it is shown that the variance of the number of solutions can be used to set bounds on the phase transition and to indicate the accuracy of the prediction. A class of sparse problems, for which the prediction is known to be inaccurate, is considered in detail; it is shown that, for these problems, the phase transition depends on the topology of the constraint graph as well as on the tightness of the constraints.

Details DOI

IJCAI Conference 1995 Conference Paper

Sparse Constraint Graphs and Exceptionally Hard Problems

  • Barbara M. Smith
  • Stuart A. Grant

Many types of problem exhibit a phase transition as a problem parameter is varied, from a region where most problems are easy and soluble to a region where most problems are easy but insoluble. In the intervening phase transition region, the median problem difficulty is greatest. However, occasional exceptionally hard problems (ehps) can be found in the easy and soluble region; these problems can be much harder than any problem occurring in the phase transition. We show that, in binary constraint satisfaction problems, ehps are much more likely to occur when the constraints are sparse than when they are dense. Ehps occur when the search algorithm encounters a large insoluble subproblem at an early stage; the exceptional difficulty is due to the cost of searching the subproblem to prove insolubility. This cost can be dramatically reduced by using conflict-directed backjumping (CBJ) rather than a chronological backtracker. However, when used with forward checking and the fail-first heuristic, it is only on ehps that CBJ gives great savings over backtracking chronologically.

PDF
v2026.09.13