An optimization problem that may be cast in the context of domain wall
s in ferromagnets and spin glasses, lattice animals, and percolation i
s described. Numerical calculations in two and three dimensions show t
hat a new universality class is obtained. In the strong disorder limit
interfaces are not self-affine but fractal. Further, the nontrivial g
round state of frustrated spin glasses is straightforwardly obtained i
n this limit.