We design a lineartimeapproximation 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 Gam...
详细信息
ISBN:
(纸本)9781605586137
We design a lineartimeapproximation 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.
暂无评论