|
Department
of |
|
Susan L. EpsteinThe CUNY Graduate School, Department
of Computer Science and Hunter College, Department
of Computer Science |
|||||
|
|
|
|
|||||
|
Home Publications Collaborators Courses Contact
|
|
PROBLEM CLASSES (CSP)A constraint satisfaction problem (CSP) is a triple <X,D,C>, where X is a finite set of variables, D is a set of domains for those variables, and C is a set of constraints, that is, restrictions on values that subsets of those variables may hold simultaneously. A solution to a CSP is an assignment of a value from each domain to its respective variable such that all the constraints are satisfied. ParameterizedA parameterized problem is a randomly-generated CSP whose constraint graph is connected. A parameterized problem is described here as <n, k, d, t>. ComposedA composed problem consists of a random central component <n ,k, d ,t> and s smaller random satellites in <n’ ,k’ ,d’ t’>. Links with density d’’ and tightness t’’ join the central component and the satellites, but there are no links between satellites. Many classes of composed problems confound traditional heuristics. A composed problem is described here as <n ,k, d ,t> s <n’ ,k’ ,d’ t’> <d’’, t’’>. GeometricA geometric problem is constructed by scattering a set of points at random on the Cartesian plane — each point becomes a variable in the problem; a constraints is formed between any pair of variables within some specified distance (D) of each other, with additional constraints added to connect the constraint graph, which is ridden with tightly connected sets of vertices. A geometric problem is described here as <n, k, D, t>. ColoringA coloring problem seeks to assign one of k colors to each vertex in a graph so that pairs of adjacent vertices have distinct colors. A coloring problem is described here as <n, k, d>. LogicA logic problem is a puzzle associated with some text. A classic example is the zebra problem: There are five houses, each of a different color and inhabited by people of different nationalities, with different pets, different favorite drinks. and different favorite cigarettes. The English person lives in the red house. The Spaniard owns a dog. Coffee is drunk in the green house. The Ukrainian drinks tea. The green house is directly to the right of the ivory house. The Old-Gold smoker owns snails. Kools are being smoked in the yellow house. Milk is drunk in the middle house. The Norwegian lives in the first house on the left. The Chesterfield smoker lives next to the fox owner. Kools are smoked in the house next to the house where the horse is kept. The Lucky-Strike smoker drinks orange juice. The Japanese person smokes Parliament. The Norwegian lives next to the blue house. Who drinks water and who owns the zebra? Each puzzle has a different formulation. N-QueensThe n-queens problem seeks to place n queens on an n ´ n chessboard so that no queen can capture any other. Quasi-GroupA quasigroup (or Latin square) problem of order n seeks to place n different symbols in an n ´ n table such that each symbol occurs exactly once in each row and exactly once in each column. A quasigroup with holes has p% of its entries (the “non-holes”) already specified. A balanced quasigroup with holes distributes those entries evenly across the rows and columns of the table. A quasigroup problem here is balanced, with p% holes, and is described here as <n, p>. Small-WorldThe characteristic path length of a graph is the length of the shortest path between two vertices, averaged over all pairs of vertices. The clustering coefficient of a graph is the average fraction of edges allowed among the neighbors of each vertex. In a small world problem, the ratio of clustering coefficient to characteristic path length is much higher than average. Small world graphs were constructed by ring lattice rewiring (Watts, D. and S. Strogatz, 1998, Collective dynamics of small-world networks. Nature 393: 440.) |
