On the approximation of maximum satisfiability

ABSTRACT

We present a 3/4 polynomial time approximation algorithm for the Maximum Satisfiability problem: Given a set of clauses, find a truth assignment that satisfies the maximum number of clauses. The algorithm applies to the weighted case as well, and involves nontrival application of network flow techniques.

REFERENCES

• AMP: G. Ausiello, A. Marchetti-Spaccamela, M. Proms, "Toward a Unified Approach for the C~: ssification of NP-complete Optimization P:~blems", 12, 83-96, (1980).
• BS: Bonnie Berger , Peter W. Shor, Approximation alogorithms for the maximum acyclic subgraph problem, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.236-243, January 22-24, 1990, San Francisco, California, United States
• BS: P. Berman , G. Schnitger, On the complexity of approximating the independent set problem, Proceedings of the 6th Annual Symposium on Theoretical Aspects of Computer Science on STACS 89, p.256-268, February 1989, Paderborn, Germany
• BP: Marshall Bern , Paul Plassmann, The steiner problem with edge lengths 1 and 2,, Information Processing Letters, v.32 n.4, p.171-176, Sept 1, 1989 [doi>10.1016/0020-0190(89)90039-2 ]
• B+: Avrim Blum , Tao Jiang , Ming Li , John Tromp , Mihalis Yannakakis, Linear approximation of shortest superstrings, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.328-336, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103455]
• C: 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]
• D+: E. Dahlhaus, D. S. Johnson, C. H. Papadimitriou, P. Seymour, M. Yannakakis, "The Complexity of Muifiway Cuts".
• E: C.S. Edwards, "An Improved Lower Bound for the Number of Edges in a Largest Bipartite Subgraph", in Recent Advances in Graph Theory (Acadomia, Praguo), 167-181, (1975).
• Er: P. Erd~3s, "On Bipartite Subgraphs of Graphs", Math. Lapok. 18, 283-288, (1967).
• EFPS: Paul Erdös , Ralph Faudree , János Pach , Joel Spencer, How to make a graph bipartite, Journal of Combinatorial Theory Series A, v.45 n.1, p.86-98, July 1987
• F: R. Fagin, "Generalized First-Order Spectra, and Polynomial-time Recognizable Sets", in R. Karp (ed.), Complexity of Computations, AMS, 1974.
• HV: David J. Haglin , Shankar M. Venkatesan, Approximation and Intractability Results for the Maximum Cut Problem and Its Variants, IEEE Transactions on Computers, v.40 n.1, p.110-113, January 1991 [doi>10.1109/12.67327 ]
• HJ: Pierre Hansen , Brigitte Jaumard, Algorithms for the maximum satisfiability problem, Computing, v.44 n.4, p.279-303, Feb. 4, 1990 [doi>10.1007/BF02241270]
• HL: Ming-Deh A. Huang , Karl J. Lieberherr, Implications of forbidden structures for extremal algorithmic problems, Theoretical Computer Science, v.40 n.2-3, p.195-210, Nov. 1985
• GJ: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• J: D.S. Johnson, "Approximation Algorithms for Combinatorial Problems", J. Comp. Sys. Sc. 9, 256-278, (1974).
• Kn: Viggo Kann, Maximum bounded 3-dimensional matching is MAX SNP-complete, Information Processing Letters, v.37 n.1, p.27-35, Jan. 10, 1991 [doi>10.1016/0020-0190(91)90246-E ]
• Kr: R.M. Karp, "Reducibility among Combinatori$~ Problems", in R. E. Miller and J. W. Thatcher (eds.), Complexity of Computer Computations, Plenum Press, 85-103, (1972).
• KARR: P~ Kloin, A, Agrawal, R. Ravi, S. Rao, "Approximation Through Multicommodity Flow", Proc. 31st Annual IEEE Symp. on Foundations of Computer Science, 726-737, (1990).
• KT: P.G. Kolaitis, M,. N. Thakur, "Approximation Properties of NP Minimization Classes", Proc, 6th Annual Conf. on Structures in Computer Sc'ence, 353-366, (1991).
• LS: K. J. Lieberherr , E. Specker, Complexity of Partial Satisfaction, Journal of the ACM (JACM), v.28 n.2, p.411-421, April 1981 [doi>10.1145/322248.322260]
• LS2: K. Lieberherr, E. Specker, "Complexity of Partial Satisfaction II", TR 293, Dept. of EECS, Princeton Univ., (1982).
• PR: A. Panconesi , D. Ranjan, Quantifiers and approximation, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.446-456, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100275]
• PY1: Christos Papadimitriou , Mihalis Yannakakis, Optimization, approximation, and complexity classes, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.229-234, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62233]
• PY2: Christos H. Papadimitriou , Mihalis Yannakakis, The traveling salesman problem with distances one and two, Mathematics of Operations Research, v.18 n.1, p.1-11, Feb. 1993
• PM: A. Paz, S. Moran, "Non Deterministic Polynomial Optimization Problems and their Approximation'', Theoretical Computer Science 15, 251-277, (1981).
• PT: S. Poljak, D. Turzik, "A Polynomial Algorithm for Constructing a Large Bipartite Subgraph, With an Application to a Satisfiability Problem'', Canadian J. of Mathematics 34(3), 519- 524, (1982).
• SG: Sartaj Sahni , Teofilo Gonzalez, P-Complete Approximation Problems, Journal of the ACM (JACM), v.23 n.3, p.555-565, July 1976 [doi>10.1145/321958.321975]
• V: P. Vitanyi, "How well Can a Graph be n- C~ lored?", Discrete Mathematics, (1981).

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Theory