Finding almost-satisfying assignments

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Finding almost-satisfying assignments

Full text

Pdf (1.24 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirtieth annual ACM symposium on Theory of computing table of contents

Dallas, Texas, United States

Pages: 551 - 560

Year of Publication: 1998

ISBN:0-89791-962-9

Author

Uri Zwick

Department of Computer Science, School of Mathematical Sciences, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv 69978, Israel

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 29, Citation Count: 10

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/276698.276869 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	N. Alon and J.H. Spencer. The probabilistic method. Wiley, 1992.
	2	Takao Asano, Approximation Algorithms for MAX SAT: Yannakakis vs. Goemans-Williamson, Proceedings of the Fifth Israel Symposium on the Theory of Computing Systems (ISTCS '97), p.24, June 17-19, 1997
	3	B. AspvaU, M.F. Plass, and R.E. Tarjan. A linear-time algorithm for testing the truth of certain quantified Boolean formulas. Information Processing Letters, 8:121-123, 1979. See errata in Information Processing Letters, 14 (1982), p. 195.
	4	Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805047]
	5	Nadia Creignou, A dichotomy theorem for maximum generalized satisfiability problems, Journal of Computer and System Sciences, v.51 n.3, p.511-522, Dec. 1995 [doi>10.1006/jcss.1995.1087]
	6	P. Crescenzi and L. Trevisan. Max NP- completeness made easy. Technic~ report, E-CCC Report number TR97-039, 1997.
	7	W. F. Dowling and J. H. Gallier. Linear-time algorithms for testing the satisfiability of propositional horn formulae. Journal of Logic Programming, 1:267-284, 1984.
	8	S. Even, A. Itai, and A. Shamlr. On the complexity of timetable and multicommodity flow problems. SIAM Journal on Computing, 5:691-703, 1976.
	9	Tomás Feder , Moshe Y. Vardi, Monotone monadic SNP and constraint satisfaction, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.612-622, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167245]
	10	Approximating the value of two power proof systems, with applications to MAX 2SAT and MAX DICUT, Proceedings of the 3rd Israel Symposium on the Theory of Computing Systems (ISTCS'95), p.182, January 04-06, 1995
	11	Naveen Garg , Vijay V. Vazirani , Mihalis Yannakakis, Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications, SIAM Journal on Computing, v.25 n.2, p.235-251, February 1996 [doi>10.1137/S0097539793243016]
	12	Michel X. Goemans , David P. Williamson, New ${\bf \frac{3}{4}}$-Approximation Algorithms for the Maximum Satisfiability Problem, SIAM Journal on Discrete Mathematics, v.7 n.4, p.656-666, Nov. 1994 [doi>10.1137/S0895480192243516]
	13	Michel X. Goemans , David P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the ACM (JACM), v.42 n.6, p.1115-1145, Nov. 1995 [doi>10.1145/227683.227684]
	14	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]
	15	D.S. Johnson. Approx-imation algorithms for combinatorical problems. Journal of Computer and System Sciences, 9:256-278, 1974.
	16	N.D. Jones and W.T. Laaser. Complete problems for deterministic polynomial time. Theoretical Coraputer Science, 3:105-117, 1976.
	17	Howard Karloff , Uri Zwick, A 7/8-Approximation Algorithm for MAX 3SAT?, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.406, October 19-22, 1997
	18	Sanjeev Khanna , Madhu Sudan , Luca Trevisan, Constraint Satisfaction: The Approximability of Minimization Problems, Proceedings of the 12th Annual IEEE Conference on Computational Complexity, p.282, June 24-27, 1997
	19	Sanjeev Khanna , Madhu Sudan , David P. Williamson, A complete classification of the approximability of maximization problems derived from Boolean constraint satisfaction, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.11-20, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258538]
	20	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]
	21	S. Mahajan , H. Ramesh, Derandomizing semidefinite programming based approximation algorithms, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.162, October 23-25, 1995
	22	Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
	23	Christos H. Papadimitriou, On selecting a satisfying truth assignment (extended abstract), Proceedings of the 32nd annual symposium on Foundations of computer science, p.163-169, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185365]
	24	Thomas J. Schaefer, The complexity of satisfiability problems, Proceedings of the tenth annual ACM symposium on Theory of computing, p.216-226, May 01-03, 1978, San Diego, California, United States [doi>10.1145/800133.804350]
	25	Luca Trevisan, Approximating Satisfiable Satisfiability Problems (Extended Abstract), Proceedings of the 5th Annual European Symposium on Algorithms, p.472-485, September 15-17, 1997
	26	L. Trevisan , G. B. Sorkin , M. Sudan , D. P. Williamson, Gadgets Approximation, and Linear Programming, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.617, October 14-16, 1996
	27	Susumu Yamasaki , Shuji Doshita, The satisfiability problem for a class consisting of Horn sentences and some non-Horn sentences in porportional logic, Information and Control, v.59 n.1-3, p.1-12, Oct./Nov./Dec. 1983 [doi>10.1016/S0019-9958(83)80027-8]
	28	Mihalis Yannakakis, On the approximation of maximum satisfiability, Journal of Algorithms, v.17 n.3, p.475-502, Nov. 1994
	29	Uri Zwick, Approximation algorithms for constraint satisfaction problems involving at most three variables per constraint, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.201-210, January 25-27, 1998, San Francisco, California, United States

CITED BY 10

	Lane A. Hemaspaandra, SIGACT news complexity theory column 43, ACM SIGACT News, v.35 n.1, March 2004
	Uri Zwick, Outward rotations: a tool for rounding solutions of semidefinite programming relaxations, with applications to MAX CUT and other problems, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.679-687, May 01-04, 1999, Atlanta, Georgia, United States
	Edward A. Hirsch, Worst-case study of local search for MAX-k-SAT, Discrete Applied Mathematics, v.130 n.2, p.173-184, 15 August 2003
	Lefteris M. Kirousis , Phokion G. Kolaitis, The complexity of minimal satisfiability problems, Information and Computation, v.187 n.1, p.20-39, November 25, 2003
	Alex Samorodnitsky , Luca Trevisan, A PCP characterization of NP with optimal amortized query complexity, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.191-199, May 21-23, 2000, Portland, Oregon, United States
	Peter Damaschke, Linear-time recognition of bipartite graphs plus two edges, Discrete Mathematics, v.262 n.1-3, p.99-112, 6 February 2003
	Subhash Khot, On the power of unique 2-prover 1-round games, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Miroslav Chlebík , Janka Chlebíková, Minimum 2SAT-DELETION: Inapproximability results and relations to Minimum Vertex Cover, Discrete Applied Mathematics, v.155 n.2, p.172-179, January, 2007
	Moses Charikar , Konstantin Makarychev , Yury Makarychev, Near-optimal algorithms for maximum constraint satisfaction problems, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.62-68, January 07-09, 2007, New Orleans, Louisiana
	Moses Charikar , Konstantin Makarychev , Yury Makarychev, Near-optimal algorithms for maximum constraint satisfaction problems, ACM Transactions on Algorithms (TALG), v.5 n.3, p.1-14, July 2009