Linear Time Approximation Schemes for the Gale-Berlekamp Game and Related Minimization Problems

Details Linear Time Approximation Schemes for the Gale-Berlekamp Game and Related Minimization Problems Linear Time Approximation Schemes for the Gale-Berlekamp Game and Related Minimization Problems

2008-11-20

arxiv.org/abs/0811.3244v1

Computer Science

Data Structures and Algorithms

18 pages LaTeX, 2 figures

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Linear Time Approximation Schemes for the Gale-Berlekamp Game and Related Minimization Problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Linear Time Approximation Schemes for the Gale-Berlekamp Game and Related Minimization Problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Linear Time Approximation Schemes for the Gale-Berlekamp Game and Related Minimization Problems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-667565