The importance of being biased

ABSTRACT

(MATH) We show that the Minimum Vertex Cover problem is NP-hard to approximate to within any factor smaller than $10\sqrt{5}-21 \approx 1.36067$, improving on the previously known hardness result for a $\frac{7}{6}$ factor.

REFERENCES

• 1: Rudolf Ahlswede , Levon H. Khachatrian, The complete intersection theorem for systems of finite sets, European Journal of Combinatorics, v.18 n.2, p.125-136, Feb. 1997 [doi>10.1006/eujc.1995.0092]
• 2: 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]
• 3: 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]
• 4: R. Bar-Yehuda and S. Even. A local-ratio theorem for approximating the weighted vertex cover problem. Annals of Discrete Mathematics, 25:27--45, 1985.
• 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: M. Ben-Or and N. Linial. Collective coin flipping. ADVCR: Advances in Computing Research, 5, 1989.
• 7: M. Ben-Or, N. Linial, and M. Saks. Collective coin flipping and other models of imperfect randomness. In Combinatorics (Eger, 1987), pages 75--112. North-Holland, Amsterdam, 1988.
• 8: I. Benjamini, G. Kalai, and O. Schramm. Noise sensitivity of Boolean functions and applications to percolation. Inst. Hautes Études Sci. Publ. Math., (90):5--43 (2001), 1999.
• 9: M. Blum , M. Luby , R. Rubinfeld, Self-testing/correcting with applications to numerical problems, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.73-83, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100225]
• 10: J. Bourgain and G. Kalai. Influences of variables and threshold intervals under group symmetries. Geom. Funct. Anal., 7(3):438--461, 1997.
• 11: 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
• 12: P. Erdös, C. Ko, and R. Rado. Intersection theorems for systems of finite sets. Quart. J. Math. Oxford Ser (2), 12:313--320, 1961.
• 13: P. Erdös and R. Rado. Intersection theorems for systems of sets. J. London Math. Soc., 35: 85--90, 1960.
• 14: U. Feige , S. Goldwasser , L. Lovász , S. Safra , M. Szegedy, Approximating clique is almost NP-complete (preliminary version), Proceedings of the 32nd annual symposium on Foundations of computer science, p.2-12, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185341]
• 15: P. Frankl. The Erdöds-Ko-Rado theorem is true for n = ckt. In Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. I, pages 365--375. North-Holland, Amsterdam, 1978.
• 16: E. Friedgut. Boolean functions with low average sensitivity depend on few coordinates. Combinatorica, 18(1):27--35, 1998.
• 17: E. Friedgut and G. Kalai. Every monotone graph property has a sharp threshold. Proc. Amer. Math. Soc., 124(10):2993--3002, 1996.
• 18: Eran Halperin, Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.329-337, January 09-11, 2000, San Francisco, California, United States
• 19: Johan Håstad, Some optimal inapproximability results, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.1-10, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258536]
• 20: J. Håstad. Clique is hard to approximate within n1-e. Acta Math., 182(1):105--142, 1999.
• 21: J. Kahn, G. Kalai, and N. Linial. The influence of variables on Boolean functions. In IEEE, editor, 29th annual Symposium on Foundations of Computer Science, October 24--26, 1988, New York, pages 68--80. IEEE Computer Society Press, 1988.
• 22: R. M. Karp. Reducibility among combinatorial problems. In Miller and Thatcher, editors, Complexity of Computer Computations, pages 85--103. Plenum Press, 1972.
• 23: 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
• 24: Philip N. Klein , Serge A. Plotkin , Satish Rao , Éva Tardos, Approximation algorithms for Steiner and directed multicuts, Journal of Algorithms, v.22 n.2, p.241-269, Feb. 1997 [doi>10.1006/jagm.1996.0833]
• 25: G. A. Margulis. Probabilistic characteristics of graphs with large connectivity. Problemy Peredači Informacii, 10(2):101--108, 1974.
• 26: Burkhard Monien , Ewald Speckenmeyer, Some Further Approximation Algorithms for the Vertex Cover Problem, Proceedings of the 8th Colloquium on Trees in Algebra and Programming, p.341-349, March 09-11, 1983
• 27: C. Papadimitriou and M. Yannakakis. Optimization, approximation and complexity classes. Journal of Computer and System Sciences, 43:425--440, 1991.
• 28: Ran Raz, A Parallel Repetition Theorem, SIAM Journal on Computing, v.27 n.3, p.763-803, June 1998 [doi>10.1137/S0097539795280895]
• 29: Ran Raz , Shmuel Safra, A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.475-484, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258641]
• 30: L. Russo. An approximate zero-one law. Z. Wahrsch. Verw. Gebiete, 61(1):129--139, 1982.
• 31: Luca Trevisan, Non-approximability results for optimization problems on bounded degree instances, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.453-461, July 2001, Hersonissos, Greece [doi>10.1145/380752.380839]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Set theory

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Numerical algorithms
      G.1.2 Approximation
          Subjects: Minimax approximation and algorithms

General Terms:
Algorithms, Experimentation, Performance, Theory