Journal of the ACM Bibliography

Preliminary version

A preliminary version of these results was presented in: Michel X. Goemans and David P. Williamson. .878-approximation algorithms for MAX CUT and MAX 2SAT. In Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, pages 422-431, Montréal, Québec, Canada, 23-25 May 1994.

Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems -- computations on discrete structures; G.2.2 [Discrete Mathematics]: Graph Theory -- graph algorithms; G.3 [Probability and Statistics] -- probabilistic algorithms (including Monte Carlo); I.1.2 [Algebraic Manipulation]: Algorithms -- analysis of algorithms

General Terms: Algorithms

Additional Key Words and Phrases: Approximation algorithms, convex optimization, randomized algorithms, satisfiability

Selected papers that cite this one

• Sameet Agarwal and Anne Condon. On approximation algorithms for hierarchical MAX-SAT. Journal of Algorithms, 26(1):141-165, January 1998.

• Gunnar Andersson and Lars Engebretsen. Better approximation algorithms for SET SPLITTING and NOT-ALL-EQUAL SAT. Information Processing Letters, 65(6):305-311, 27 March 1998.

• Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems. Journal of the ACM, 45(3):501-555, May 1998.

• T. Asano, T. Ono, and T. Hirata. Approximation Algorithms for the Maximum Satisfiability Problem Nordic Journal of Computing, 3(4):388-404, Winter 1996.

• Mihir Bellare, Oded Goldreich, and Madhu Sudan. Free bits, PCPs, and nonapproximability -- towards tight results. SIAM Journal on Computing, 27(3):804-915, June 1998.

• Steven Homer and Marcus Peinado. Design and performance of parallel and distributed approximation algorithms for Maxcut. Journal of Parallel and Distributed Computing, 46(1):48-61, 1 October 1997.

• Viggo Kann, Jens Lagergren, and Alessandro Panconesi. Approximability of maximum splitting of k-sets and some other Apx-complete problems. Information Processing Letters, 58(3):105-110, 13 May 1996.

• David Karger, Rajeev Motwani, and Madhu Sudan. Approximate graph coloring by semidefinite programming. Journal of the ACM, 45(2):246-265, March 1998.

• Howard Karloff. How good is the Goemans-Williamson MAX CUT algorithm? In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, pages 427-434, Philadelphia, Pennsylvania, 22-24 May 1996.

• Howard Karloff and Uri Zwick. A 7/8-approximation algorithm for MAX 3SAT? In 38th Annual Symposium on Foundations of Computer Science, pages 406-415, Miami Beach, Florida, 20-22 October 1997. IEEE.

• Sanjeev Khanna, Madhu Sudan, and David P. Williamson. A complete classification of the approximability of maximization problems derived from Boolean constraint satisfaction. In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pages 11-20, El Paso, Texas, 4-6 May 1997.

• Samir Khuller. Problems. Journal of Algorithms, 28(1):192-195, July 1998.

• Madhav V. Marathe, Harry B. Hunt III, Richard E. Stearns, and Venkatesh Radhakrishnan. Approximation algorithms for PSPACE-hard hierarchically and periodically specified problems. SIAM Journal on Computing, 27(5):1237-1261, October 1998.

• L. Trevisan. Parallel approximation algorithms by positive linear programming. Algorithmica, 21(1):72-88, May 1998.

• Luca Trevisan, Gregory B. Sorkin, Madhu Sudan, and David P. Williamson. Gadgets, approximation, and linear programming (extended abstract). In 37th Annual Symposium on Foundations of Computer Science, pages 617-626, Burlington, Vermont, 14-16 October 1996. IEEE.

• Uri Zwick. Approximation algorithms for constraint satisfaction problems involving at most three variables per constraint. In Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 201-210, San Francisco, California, 25-27 January 1998.

Selected references

• Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and hardness of approximation problems. In 33rd Annual Symposium on Foundations of Computer Science, pages 14-23, Pittsburgh, Pennsylvania, 24-27 October 1992. IEEE.

• R. Bar-Yehuda and S. Even. A linear-time approximation algorithm for the weighted vertex cover problem. Journal of Algorithms, 2(2):198-203, June 1981.

• Mihir Bellare, Oded Goldreich, and Madhu Sudan. Free bits, PCPs and non-approximability -- towards tight results. In 36th Annual Symposium on Foundations of Computer Science, pages 422-431, Milwaukee, Wisconsin, 23-25 October 1995. IEEE.

• Uriel Feige and László Lovász. Two-prover one-round proof systems: Their power and their problems (extended abstract). In Proceedings of the Twenty-Fourth Annual ACM Symposium on the Theory of Computing, pages 733-744, Victoria, British Columbia, Canada, 4-6 May 1992.

• Michel X. Goemans and David P. Williamson. .878-approximation algorithms for MAX CUT and MAX 2SAT. In Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, pages 422-431, Montréal, Québec, Canada, 23-25 May 1994.

• David Karger, Rajeev Motwani, and Madhu Sudan. Approximate graph coloring by semidefinite programming. In 35th Annual Symposium on Foundations of Computer Science, pages 2-13, Santa Fe, New Mexico, 20-22 November 1994. IEEE.

• Sanjeev Mahajan and H. Ramesh. Derandomizing semidefinite programming based approximation algorithms. In 36th Annual Symposium on Foundations of Computer Science, pages 162-169, Milwaukee, Wisconsin, 23-25 October 1995. IEEE.

• Christos H. Papadimitriou and Mihalis Yannakakis. Optimization, approximation, and complexity classes. Journal of Computer and System Sciences, 43(3):425-440, December 1991.

• Sartaj Sahni and Teofilo Gonzalez. P-complete approximation problems. Journal of the ACM, 23(3):555-565, July 1976.

• Pravin M. Vaidya. A new algorithm for minimizing convex functions over convex sets (extended abstract). In 30th Annual Symposium on Foundations of Computer Science, pages 338-343, Research Triangle Park, North Carolina, 30 October-1 November 1989. IEEE.

• Mihalis Yannakakis. On the approximation of maximum satisfiability. Journal of Algorithms, 17(3):475-502, November 1994.

Shortcuts: