Next: MINIMUM ATTRACTION RADIUS FOR
Up: Miscellaneous
Previous: MINIMUM TREE ALIGNMENT
  Index
- INSTANCE:
Finite alphabet ,
finite string s from .
- SOLUTION:
A folding of s in the 3-dimensional rectangular grid ,
that is, a mapping of s into
such that adjacent symbols
of s are adjacent in the lattice, and no site in the lattice is
occupied by more than one symbol.
- MEASURE:
The number of pairs of equal symbols that lie at adjacent
lattice sites (excluding pairs that are adjacent in s).
- Bad News:
APX-hard under randomized polynomial time reductions [385].
Viggo Kann
2000-03-20