MAX-SAT for Formulas with Constant Clause Density Can Be Solved Faster Than in \(\mathcal{O}(2^n)\) Time

1. Arvind, V., Schuler, R.: The quantum query complexity of 0-1 knapsack and associated claw problems. In: Ibaraki, T., Katoh, N., Ono, H. (eds.) ISAAC 2003. LNCS, vol. 2906, pp. 168–177. Springer, Heidelberg (2003)

   Chapter  Google Scholar 

2. 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)

   Chapter  Google Scholar 

3. Beame, P., Impagliazzo, R., Pitassi, T., Segerlind, N.: Memoization and DPLL: Formula caching proof systems. In: Proceedings of the 18th Annual IEEE Conference on Computational Complexity, CCC 2003, pp. 225–236 (2003)

   Google Scholar 

4. Cai, L., Chen, J.: On fixed-parameter tractability and approximability of NP optimization problems. Journal of Computer and System Sciences 54(3), 465–474 (1997)

   Article  MATH  MathSciNet  Google Scholar 

5. Chen, J., Kanj, I.: Improved exact algorithm for Max-Sat. Discrete Applied Mathematics 142(1-3), 17–27 (2004)

   Article  MATH  MathSciNet  Google Scholar 

6. Dantsin, E., Gavrilovich, M., Hirsch, E.A., Konev, B.: MAX SAT approximation beyond the limits of polynomial-time approximation. Annals of Pure and Applied Logic 113(1-3), 81–94 (2001)

   Article  MathSciNet  Google Scholar 

7. Graham, R., Knuth, D., Patashnik, O.: Concrete Mathematics: A Foundation for Computer Science, 2nd edn. Addison-Wesley, Reading (1994)

   MATH  Google Scholar 

8. Hirsch, E.A.: Worst-case study of local search for MAX-k-SAT. Discrete Applied Mathematics 130(2), 173–184 (2003)

   Article  MATH  MathSciNet  Google Scholar 

9. Karloff, H., Zwick, U.: A 7/8-approximation algorithm for MAX 3SAT? In: Proceedings of the 38th Annual IEEE Symposium on Foundations of Computer Science, FOCS 1997, pp. 406–415 (1997)

   Google Scholar 

10. Mahajan, M., Raman, V.: Parameterizing above guaranteed values: Maxsat and maxcut: An algorithm for the satisfiability problem of formulas in conjunctive normal form. Journal of Algorithms 31(2), 335–354 (1999)

    Article  MATH  MathSciNet  Google Scholar 

11. Monien, B., Speckenmeyer, E.: Upper bounds for covering problems. Technical Report Bericht Nr. 7/1980, Reihe Theoretische Informatik, Universität-Gesamthochschule-Paderborn (1980)

    Google Scholar 

12. Niedermeier, R., Rossmanith, P.: New upper bounds for maximum satisfiability. Journal of Algorithms 36(1), 63–88 (2000)

    Article  MATH  MathSciNet  Google Scholar 

13. Williams, R.: On computing k-CNF formula properties. In: Giunchiglia, E., Tacchella, A. (eds.) SAT 2003. LNCS, vol. 2919, pp. 330–340. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

14. Zhang, H., Shen, H., Manyà, F.: Exact algorithms for MAX-SAT. Electronic Notes in Theoretical Computer Science 86(1) (May 2003)

    Google Scholar 

Download references