Abstract
We show how to check whether at least k clauses of an input formula in CNF can be satisfied in time O *(1.358k). This improves the bound O *(1.370k) proved by Chen and Kanj more than 10 years ago. Though the presented algorithm is based on standard splitting techniques its core are new simplification rules that often allow to reduce the size of case analysis. Our improvement is based on a simple algorithm for a special case of MAX-SAT where each variable appears at most 3 times.
Research is partially supported by Federal Target Program “Scientific and scientific-pedagogical personnel of the innovative Russia” 2009–2013 and Russian Foundation for Basic Research.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Chen, J., Kanj, I.A.: Improved Exact Algorithms for MAX-SAT. In: Rajsbaum, S. (ed.) LATIN 2002. LNCS, vol. 2286, pp. 341–355. Springer, Heidelberg (2002)
Mahajan, M., Raman, V.: Parameterizing above guaranteed values: MaxSat and MaxCut. J. Algorithms 31(2), 335–354 (1999)
Niedermeier, R., Rossmanith, P.: New Upper Bounds for MaxSat. In: Wiedermann, J., Van Emde Boas, P., Nielsen, M. (eds.) ICALP 1999. LNCS, vol. 1644, pp. 575–584. Springer, Heidelberg (1999)
Bansal, N., Raman, V.: Upper Bounds for MaxSat: Further Improved. In: Aggarwal, A.K., Pandu Rangan, C. (eds.) ISAAC 1999. LNCS, vol. 1741, pp. 247–258. Springer, Heidelberg (1999)
Alon, N., Gutin, G., Kim, E., Szeider, S., Yeo, A.: Solving MAX-r-SAT Above a Tight Lower Bound. Algorithmica 61, 638–655 (2011)
Crowston, R., Gutin, G., Jones, M., Yeo, A.: A New Lower Bound on the Maximum Number of Satisfied Clauses in Max-SAT and Its Algorithmic Applications. Algorithmica 64(1), 56–68 (2012)
van Rooij, J.M., Bodlaender, H.L.: Exact algorithms for dominating set. Discrete Applied Mathematics 159(17), 2147–2164 (2011)
Kulikov, A., Kutzkov, K.: New Bounds for MAX-SAT by Clause Learning. In: Diekert, V., Volkov, M.V., Voronkov, A. (eds.) CSR 2007. LNCS, vol. 4649, pp. 194–204. Springer, Heidelberg (2007)
Bliznets: A New Upper Bound for (n,3)-MAX-SAT. Zapiski Nauchnikh Seminarov POMI, 5–14 (2012)
Lieberherr, K.J., Specker, E.: Complexity of Partial Satisfaction. J. ACM 28, 411–421 (1981)
Yannakakis, M.: On the approximation of maximum satisfiability. In: SODA 1992, pp. 1–9 (1992)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bliznets, I., Golovnev, A. (2012). A New Algorithm for Parameterized MAX-SAT. In: Thilikos, D.M., Woeginger, G.J. (eds) Parameterized and Exact Computation. IPEC 2012. Lecture Notes in Computer Science, vol 7535. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-33293-7_6
Download citation
DOI: https://doi.org/10.1007/978-3-642-33293-7_6
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-33292-0
Online ISBN: 978-3-642-33293-7
eBook Packages: Computer ScienceComputer Science (R0)