Fall Semester, 2001
CSCE421/821: Foundations of Constraint Satisfaction

Homework 4

Assignment date: Thursday, November 28th 2001
Due date: Thursday, December 6th, 2001
Total value: 80 points.

Question 1: Mapping between representations                                             (50 points)

(Adapted from an example of Bessière's invited talk at CP-99)

The worst-case complexity of AC-4 on a binary representation is O(e.d2),  where d the domain size and e the number of binary constraints. More precisely, it is O(e.d1.d2), where d1, d2 are the maximum size of any two variables linked by a constraint.

Consider a non-binary CSP, with n variables, d domain size (values per variable domain), e constraints, each of arity <=k.

  • (2x5 points) Describe the two general techniques of mapping the non-binary CSP into a binary one.
  • For each resulting binary representation, determine, in terms of n, d, e, or k of the original non-binary representation:
    • Warning:  there are two types of variables in the hidden representation technique.  Determine the domain size of each of them and take this into account when computing the complexity of AC-4 in this case.
     

    Question 2:  Glossary                                  (Value 30 points)
    Write down the definitions of the following terms.  Provide references for each definition when applicable. (2 points per term.)

    1. Chromatic number
    2. Constraint network of order k (Freuder's terminology)
    3. Graph reduction operators
    4. Hamiltonian circuit
    5. K-colorability  (decision, optimization)
    6. K-consistency
    7. Least discrepancy search
    8. Makespan (optimization criterion)
    9. Order parameter
    10. Phase transition
    11. Schedule packing optimization algorithm
    12. Squeaky wheel optimization algorithm
    13. Tabu (a.k.a. taboo, tabou) search
    14. Traveling sales person problem
    15. WalkSat
    Berthe Y. Choueiry