Journal of the ACM Bibliography

Preliminary version

A preliminary version of these results was presented in: Carsten Lund and Mihalis Yannakakis. On the hardness of approximating minimization problems (extended abstract). In Proceedings of the Twenty-Fifth Annual ACM Symposium on the Theory of Computing, pages 286-293, San Diego, California, 16-18 May 1993.

Selected papers that cite this one

• Edoardo Amaldi and Viggo Kann. On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems. Theoretical Computer Science, 209(1-2):237-260, 6 December 1998.

• Sanjeev Arora, László Babai, Jacques Stern, and Z. Sweedyk. The hardness of approximate optima in lattices, codes, and systems of linear equations. Journal of Computer and System Sciences, 54(2):317-331, April 1997.

• 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.

• Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs: A new characterization of NP. Journal of the ACM, 45(1):70-122, January 1998.

• 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.

• Richard Chang. On the query complexity of clique size and maximum satisfiability. Journal of Computer and System Sciences, 53(2):298-313, October 1996.

• Richard Chang, William I. Gasarch, and Carsten Lund. On bounded queries and approximation. SIAM Journal on Computing, 26(1):188-209, January 1997.

• Jianer Chen, Saroja P. Kanchi, and Arkady Kanevsky. A note on approximating graph genus. Information Processing Letters, 61(6):317-322, 28 March 1997.

• Anne Condon, Joan Feinberg, Carsten Lund, and Peter Shor. Random debaters and the hardness of approximating stochastic functions. SIAM Journal on Computing, 26(2):369-400, April 1997.

• Uriel Feige. A threshold of ln n for approximating set cover (preliminary version). In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, pages 314-318, Philadelphia, Pennsylvania, 22-24 May 1996.

• Uriel Feige, Shafi Goldwasser, Laszlo Lovász, Shmuel Safra, and Mario Szegedy. Interactive proofs and the hardness of approximating cliques. Journal of the ACM, 43(2):268-292, March 1996.

• Uriel Feige and Joe Kilian. Zero knowledge and the chromatic number. Journal of Computer and System Sciences, 57(2):187-199, October 1998.

• Shafi Goldwasser. New directions in cryptography: Twenty some years later (or Cryptography and complexity theory: A match made in heaven). In 38th Annual Symposium on Foundations of Computer Science, pages 314-324, Miami Beach, Florida, 20-22 October 1997. IEEE.

• Sudipto Guha and Samir Khuller. Greedy strikes back: Improved facility location algorithms. In Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 649-657, San Francisco, California, 25-27 January 1998.

• S. Guha and S. Khuller. Approximation algorithms for connected dominating sets. Algorithmica, 20(4):374-387, April 1998.

• Sudipto Guha and Samir Khuller. Improved methods for approximating node weighted Steiner trees and connected dominating sets. Accepted for publication in Information and Computation. Final manuscript received for publication July 22, 1998.

• 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.

• Ran Raz and Shmuel Safra. A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pages 475-484, El Paso, Texas, 4-6 May 1997.

• Carsten Rössner and Jean-Pierre Seifert. On the hardness of approximating shortest integer relations among rational numbers. Theoretical Computer Science, 209(1-2):287-297, 6 December 1998.

• Petr Slavík. A tight analysis of the greedy algorithm for set cover. Journal of Algorithms, 25(2):237-254, November 1997.

• Petr Slavík. A tight analysis of the greedy algorithm for set cover. In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, pages 435-441, Philadelphia, Pennsylvania, 22-24 May 1996.

• Aravind Srinivasan. Improved approximations of packing and covering problems. In Proceedings of the Twenty-Seventh Annual ACM Symposium on the Theory of Computing, pages 268-276, Las Vegas, Nevada, 29 May-1 June 1995.

• Mikkel Thorup. All structured programs have small tree-width and good register allocation. Information and Computation, 142(2):159-181, 1 May 1998.

Selected references

• Noga Alon, Oded Goldreich, Johan Håstad, and René Peralta. Simple constructions of almost k-wise independent random variables. In 31st Annual Symposium on Foundations of Computer Science, volume II, pages 544-553, St. Louis, Missouri, 22-24 October 1990. IEEE.

• 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.

• Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs; a new characterization of NP. In 33rd Annual Symposium on Foundations of Computer Science, pages 2-13, Pittsburgh, Pennsylvania, 24-27 October 1992. IEEE.

• M. Bellare, S. Goldwasser, C. Lund, and A. Russell. Efficient probabilistically checkable proofs and applications to approximation. In Proceedings of the Twenty-Fifth Annual ACM Symposium on the Theory of Computing, pages 294-304, San Diego, California, 16-18 May 1993.

• Avrim Blum. Some tools for approximate 3-coloring (extended abstract). In 31st Annual Symposium on Foundations of Computer Science, volume II, pages 554-562, St. Louis, Missouri, 22-24 October 1990. IEEE.

• U. Feige, S. Goldwasser, L. Lovász, S. Safra, and M. Szegedy. Approximating clique is almost NP-complete (preliminary version). In 32nd Annual Symposium on Foundations of Computer Science, pages 2-12, San Juan, Puerto Rico, 1-4 October 1991. 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.

• M. R. Garey and D. S. Johnson. The complexity of near-optimal graph coloring. Journal of the ACM, 23(1):43-49, January 1976.

• Dror Lapidot and Adi Shamir. Fully parallelized multi prover protocols for NEXP-time (extended abstract). In 32nd Annual Symposium on Foundations of Computer Science, pages 13-18, San Juan, Puerto Rico, 1-4 October 1991. IEEE.

• Nati Linial and Umesh Vazirani. Graph products and chromatic numbers. In 30th Annual Symposium on Foundations of Computer Science, pages 124-128, Research Triangle Park, North Carolina, 30 October-1 November 1989. IEEE.

• Christos H. Papadimitriou and Mihalis Yannakakis. Optimization, approximation, and complexity classes (extended abstract). In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, pages 229-234, Chicago, Illinois, 2-4 May 1988.

• Avi Wigderson. Improving the performance guarantee for approximate graph coloring. Journal of the ACM, 30(4):729-735, October 1983.

• Mihalis Yannakakis. The effect of a connectivity requirement on the complexity of maximum subgraph problems. Journal of the ACM, 26(4):618-630, October 1979.

Shortcuts: