Department of
Computer Science
695 Park Ave.
NY, NY 10021

 

Susan L. Epstein

The 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.   

Parameterized

A parameterized problem is a randomly-generated CSP whose constraint graph is connected. A parameterized problem is described here as <n, k, d, t>.

Composed

A 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’’>.

Geometric

A 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>.

Coloring

A 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>.

Logic

A 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-Queens

The n-queens problem seeks to place n queens on an n ´ n chessboard so that no queen can capture any other.

Quasi-Group

A 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-World

The 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.)

[top of the page]

Home