Linear time approximation schemes for the Gale-Berlekamp game and related minimization problems

ABSTRACT

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.

REFERENCES

• 1: Nir Ailon , Moses Charikar, Fitting tree metrics: Hierarchical clustering and Phylogeny, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.73-82, October 23-25, 2005 [doi>10.1109/SFCS.2005.36]
• 2: Noga Alon , W. Fernandez de la Vega , Ravi Kannan , Marek Karpinski, Random sampling and approximation of MAX-CSP problems, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509945]
• 3: N. Alon, R. Panigrahy, and S. Yekhanin. Deterministic Approximation Algorithms for the Nearest Codeword Problem. Technical report, Elec. Coll. on Comp. Compl., ECCC TR08--065, 2008.
• 4: Sanjeev Arora , László Babai , Jacques Stern , Z. Sweedyk, The hardness of approximate optima in lattices, codes, and systems of linear equations, Journal of Computer and System Sciences, v.54 n.2, p.317-331, April 1997 [doi>10.1006/jcss.1997.1472]
• 5: A. Frieze, A new rounding procedure for the assignment problem with applications to dense graph arrangement problems, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.21, October 14-16, 1996
• 6: Sanjeev Arora , David Karger , Marek Karpinski, Polynomial time approximation schemes for dense instances of NP-hard problems, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.284-293, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225140]
• 7: Cristina Bazgan , W. Fernandez de la Vega , Marek Karpinski, Polynomial time approximation schemes for dense instances of minimum constraint satisfaction, Random Structures & Algorithms, v.23 n.1, p.73-91, August 2003 [doi>10.1002/rsa.10072]
• 8: Piotr Berman , Marek Karpinski, Approximating minimum unsatisfiability of linear equations, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.514-516, January 06-08, 2002, San Francisco, California
• 9: Piotr Berman , Marek Karpinski, Approximation Hardness of Bounded Degree MIN-CSP and MIN-BISECTION, Proceedings of the 29th International Colloquium on Automata, Languages and Programming, p.623-632, July 08-13, 2002
• 10: J. Carlson and D. Stolarski. The Correct Solution to Berlekamp's Switching Game. Discrete Mathematics, 287(1--3):145--150, 2004.
• 11: I. Dinur , G. Kindler , R. Raz , S. Safra, Approximating CVP to Within Almost-Polynomial Factors is NP-Hard, Combinatorica, v.23 n.2, p.205-243, April 2003 [doi>10.1007/s00493-003-0019-y]
• 12: Uriel Feige , László Lovász, Two-prover one-round proof systems: their power and their problems (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.733-744, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129783]
• 13: W. Fernandez de la Vega, MAX-CUT has a randomized approximation scheme in dense graphs, Random Structures & Algorithms, v.8 n.3, p.187-198, May 1996 [doi>10.1002/(SICI)1098-2418(199605)8:3<187::AID-RSA3>3.0.CO;2-U]
• 14: W. Fernandez de la Vega, R. Kannan, and M. Karpinski. Approximation of Global MAX-CSP Problems. Technical Report TR06-124, Electronic Colloquim on Computation Complexity, 2006.
• 15: P. C. Fishburn , N. J. Sloane, The solution to Berlekamp's switching game, Discrete Mathematics, v.74 n.3, p.263-290, April 1989 [doi>10.1016/0012-365X(89)90141-6]
• 16: A. M. Frieze and R. Kannan. Quick Approximation to Matrices and Applications. Combinatorica, 19(2):175--220, 1999.
• 17: I. Giotis and V. Guruswami. Correlation clustering with a fixed number of clusters. Theory of Computing, 2(1):249--266, 2006.
• 18: Anupam Gupta , Kunal Talwar, Approximating unique games, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.99-106, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109569]
• 19: S. V. Lokam, Spectral methods for matrix rigidity with applications to size-depth tradeoffs and communication complexity, Proceedings of the 36th Annual Symposium on Foundations of Computer Science, p.6, October 23-25, 1995
• 20: Claire Mathieu , Warren Schudy, Yet another algorithm for dense max cut: go greedy, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.176-182, January 20-22, 2008, San Francisco, California
• 21: R. Roth and K. Viswanathan. On the Hardness of Decoding the Gale-Berlekamp Code. IEEE Transactions on Information Theory, 54(3):1050--1060, March 2008.
• 22: Mark Rudelson , Roman Vershynin, Sampling from large matrices: An approach through geometric functional analysis, Journal of the ACM (JACM), v.54 n.4, p.21-es, July 2007 [doi>10.1145/1255443.1255449]
• 23: J. Spencer. Ten Lectures on the Probabilistic Method. SIAM, Regional Conference Series, second edition, 1994.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Algorithms, Theory

Keywords:
Gale-Berlekamp game, approximation algorithms, correlation and hierarchical clustering, dense instances, linear time approximation schemes, minimum constraint satisfaction, nearest codeword problem