Next: MINIMUM ATTRACTION RADIUS FOR Up: Miscellaneous Previous: MINIMUM TREE ALIGNMENT Index

### MAXIMUM STRING FOLDING

- INSTANCE: Finite alphabet , finite string s from .

- SOLUTION: A folding of s in the 3-dimensional rectangular grid Z3, that is, a mapping of s into Z3 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 [364].