On the advantage over a random assignment

ABSTRACT

We initiate the study of a new measure of approximation. This measure compares the performance of an approximation algorithm to the random assignment algorithm. Since the random assignment algorithm is known to give essentially the best possible polynomial time approximation algorithm for many optimization problems, this is a useful measure.In this paper, we focus on this measure for the optimization problems, Max-Lin-2, in which we need to maximize the number of satisfied linear equations in a system of linear equations modulo 2, and Max-$k$-Lin-2, a special case of the above problem in which each equation has at most $k$ variables. The main techniques we use, in our approximation algorithms and inapproximability results for this measure, are from Fourier analysis and derandomization.

REFERENCES

• 1: Noga Alon , Uriel Feige , Avi Wigderson , David Zuckerman, Derandomized graph products, Computational Complexity, v.5 n.1, p.60-75, Jan. 1995 [doi>10.1007/BF01277956]
• 2: N. Alon and J. Spencer, The Probabilistic Method, Wiley-Inter science Series, 2000.
• 3: Sanjeev Arora , Carsten Lund , Rajeev Motwani , Madhu Sudan , Mario Szegedy, Proof verification and the hardness of approximation problems, Journal of the ACM (JACM), v.45 n.3, p.501-555, May 1998 [doi>10.1145/278298.278306]
• 4: Sanjeev Arora , Shmuel Safra, Probabilistic checking of proofs: a new characterization of NP, Journal of the ACM (JACM), v.45 n.1, p.70-122, Jan. 1998 [doi>10.1145/273865.273901]
• 5: Mihir Bellare , Oded Goldreich , Madhu Sudan, Free Bits, PCPs, and Nonapproximability---Towards Tight Results, SIAM Journal on Computing, v.27 n.3, p.804-915, June 1998 [doi>10.1137/S0097539796302531]
• 6: Mihir Bellare , Phillip Rogaway, The complexity of approximating a nonlinear program, Mathematical Programming: Series A and B, v.69 n.3, p.429-441, Sept. 28, 1995 [doi>10.1007/BF01585569]
• 7: J. Bourgain, Walsh subspaces of lp product spaces. In Seminaire D'Analyse Fonctionnelle. Ecole Polytechnique, Centre De (MATH)ematiques, 1979-80, pp 4.1--4.9.
• 8: Avrim Blum , Adam Kalai , Hal Wasserman, Noise-tolerant learning, the parity problem, and the statistical query model, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.435-440, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335355]
• 9: Lars Engebretsen , Jonas Holmerin, Clique Is Hard to Approximate within n1-o(1), Proceedings of the 27th International Colloquium on Automata, Languages and Programming, p.2-12, July 09-15, 2000
• 10: Subhash Khot, Hardness results for approximate hypergraph coloring, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509962]
• 11: S. Khot, Improved Inapproximability Results for MaxClique, Chromatic Number and Approximate Graph Coloring, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.600, October 14-17, 2001
• 12: Johan Håstad, Some optimal inapproximability results, Journal of the ACM (JACM), v.48 n.4, p.798-859, July 2001 [doi>10.1145/502090.502098]
• 13: A. Lubotzky, R. Philips and P. Sarnak, Ramanujan Graphs, Combinatorica, 8(3), 1988, pages 261--277.
• 14: Ran Raz, A Parallel Repetition Theorem, SIAM Journal on Computing, v.27 n.3, p.763-803, June 1998 [doi>10.1137/S0097539795280895]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Rational approximation

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Random number generation

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.1 Expressions and Their Representation
          Subjects: Representations (general and polynomial)

General Terms:
Algorithms, Experimentation, Performance, Theory