  We design a linear time approximation scheme for the Gale-Berlekamp Switching
Game and generalize it to a wider class of dense fragile minimization problems
including the Nearest Codeword Problem (NCP) and Unique Games Problem. Further
applications include, among other things, finding a constrained form of matrix
rigidity and maximum likelihood decoding of an error correcting code. As
another application of our method we give the first linear time approximation
schemes for correlation clustering with a fixed number of clusters and its
hierarchical generalization. Our results depend on a new technique for dealing
with small objective function values of optimization problems and could be of
independent interest.
