Uri Zwick
- 1.N. Alon and J.H. Spencer. The probabilistic method. Wiley, 1992.Google Scholar
- 2.T. Asano. Approximation algorithms for MAX SAT: Yannakakis vs. Ooemans-Williamson. In Proc. of the 3nd Israel Symposium on Theory and Gomputing Systems, Ramat Gan, Israel, pages 24- 37, 1997. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 4.$.A. Cook. The complexity of theorem-provingprocedures. In Proc. of the 3rd Annual A CM Symposium on Theory of Computing, Shaker Heights, Ohio, pages 151-158, 1971. Google ScholarDigital Library
- 5.N. Creignou. A dichotomy theorem for maximum generalized satisfiability problems. Journal of Computer and System Sciences, 51:511-522, 1995. Google ScholarDigital Library
- 6.P. Crescenzi and L. Trevisan. Max NP- completeness made easy. Technic~ report, E-CCC Report number TR97-039, 1997.Google Scholar
- 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.Google ScholarCross Ref
- 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.Google ScholarCross Ref
- 9.T. Feder and M.Y. Vardi. Monotone monadic SNP and constraint satisfaction. In Proc. of the 25rd Annual A CM Symposium on Theory of Computing, San Diego, California, pages 612-622, 1993. Google ScholarDigital Library
- 10.U. Feige and M.X. Goemans. Approximating the x~lue of two prover proof systems, with applications to MAX-2SAT and MAX-DICUT. In Proc. of the 3nd Israel Symposium on Theory and Computing Systems, Tel Aviv, Israel, pages 182-189, 1995. Google ScholarDigital Library
- 11.N. Garg, V.V. Vazirani, and M. Yannakakis. Approximate max-flow min- (multi) cut theorems and their applications. SIAM Journal on Computing, 25:235-251, 1996. Google ScholarDigital Library
- 12.M.X. Goemans and D.P. Williamson. New 3/4- approx-imation algorithms for the maximum satisfiability problem. SIAM journal on Discrete Mathematics, 7:656-666, 1994. Google ScholarDigital Library
- 13.M.X. Goemans and D.P. Williamson. Improved appro~mation algorithms for maximum cut. and sat isfiability problems using semidefinite programming. Journal of the ACM, 42:1115-1145, 1995. Google ScholarDigital Library
- 14.J. H~stad. Some optimal inapproxSmability results. In Proc. of the ~Sth Annual A CM Symposium on Theory of Computing, El Paso, Texas, pages 1- 10, 1997. Full version awailable as F_,-CCC Report number TR97-037. Google ScholarDigital Library
- 15.D.S. Johnson. Approx-imation algorithms for combinatorical problems. Journal of Computer and System Sciences, 9:256-278, 1974.Google ScholarDigital Library
- 16.N.D. Jones and W.T. Laaser. Complete problems for deterministic polynomial time. Theoretical Coraputer Science, 3:105-117, 1976.Google ScholarCross Ref
- 17.H. Karloff and U. Zwick. A 7/8-approxSmation algorithm for MAX 3SAT? in Proc. of the 38rd Annual IEEE Symposium on Foundations of Computer Science, Miami Beach, Florida, pages 406-415, 1997. Google ScholarDigital Library
- 18.S. Khanna, M. Sudan, and L. Trevisan. Constraint satisfaction: The appro.xqmab~ty of minimization problems. In Proc. of the 12th Annual IEEE Conference on Computational Complexity, Ulm, Germany, pages 282-296, 1997. Full version available as E-CCC Report number TR96-064. Google ScholarDigital Library
- 19.S. Khanna, M. Sudan, and D.P. Williamson. A complete classification of the approximability of maximization problems derived from Boolean constraint satisfaction. In Proc. of the ~Sth Annual A CM Symposium on Theory of Computing, El Paso, Texas, pages 11-20, 1997. Full version available as E-CCC Report number TR96-062. Google ScholarDigital Library
- 20.P.N. Klein, S.A. Plotkin, S. Rao, and t~. Tardos. Approximation algorithms for Steiner and directed multicuts. Journal of Algorithms, 22:241-269, 1997. Google ScholarDigital Library
- 21.S. Mahajan and H. Ramesh. Derandomizing semidefinite programming based approximation algorithms. In Proc. of the 36rd Annual IEEE Symposium on Foundations of Computer Science, Milwaukee~ Wisconsin, pages 162-169, 1995. Google ScholarDigital Library
- 22.R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995. Google ScholarDigital Library
- 23.C.H. Papadimitriou. On selecting a satisfying truth assignment. In Proc. of the 32rd Annual IEEE Symposium on Foundations of Computer Science, San Juan, Puerto Rico, pages 163-169, 1991. Google ScholarDigital Library
- 24.T.J. Schaefer. The complexity of satisfiability problems. In Proc. of the lOth Annual ACM Symposium on Theory of Computing, Sa~ Diego, California, pages 216-226, 1978. Google ScholarDigital Library
- 25.L. Trevisan. Approximating satisfiable satisfiability problems. In Proc. of the 5th European Symposium on Algorithms, Graz, Austria, 1997. 472-485. Google ScholarDigital Library
- 26.L. Trevisan, G.B. Sorkin, M. Sudan, and D.P. Williamson. Gadgets, approximation, and linear programming. In Proc. of the 37rd Annual IEEE Symposium on Foundations of Computer Science, Burlington, Vermont, pages 617-626, 1996. Google ScholarDigital Library
- 27.S. Yamasaki and S. Doshita. The satisfiability problem for a class consisting of Horn sentences and some non-Horn sentences in proportionallogic. Information and Control, 59:1-12, 1983. See errata in Information and Control 61 (1984), p. 174. Google ScholarDigital Library
- 28.M. Yannakakis. On the approximation of m~ximum satisfiability. Journal o} Algorithms, 17:475-502, 1994. Google ScholarDigital Library
- 29.U. Zwick. Approximation algorithms for constraint satisfaction problems involving at most three variables per constraint. In Proe. of the 9th Annual A CM-SIAM Symposium on Discrete Algorithma, San Francisco, California, pages 201-210, 1998. Google ScholarDigital Library
Index Terms
- Finding almost-satisfying assignments
Recommendations
Nifty Assignments
SIGCSE '15: Proceedings of the 46th ACM Technical Symposium on Computer Science EducationA great CS assignment is a delight to all, but the path to one can be most roundabout. Many CS students have had their characters built up on assignments that worked better as an idea than as an actual assignment. Assignments are hard to come up with, ...
Nifty Assignments
SIGCSE '16: Proceedings of the 47th ACM Technical Symposium on Computing Science EducationI suspect that students learn more from our programming assignments than from our much sweated-over lectures, with their slide transitions, clip art, and joke attempts. A great assignment is deliberate about where the student hours go, concentrating the ...
Nifty Assignments
SIGCSE '21: Proceedings of the 52nd ACM Technical Symposium on Computer Science EducationThe Nifty Assignments special session is about promoting and sharing the ideas and ready-to-use materials of successful assignments.
Each presenter will introduce their assignment, give a quick demo, and describe its niche in the curriculum and its ...
Comments