Top

Published in:

2018 | OriginalPaper | Chapter

Upper and Lower Bounds for Different Parameterizations of (n,3)-MAXSAT

Authors : Tatiana Belova, Ivan Bliznets

Published in: Combinatorial Optimization and Applications

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

In this paper, we consider the (n,3)-MAXSAT problem. The problem is a special case of the Maximum Satisfiability problem with an additional requirement that in input formula each variable appears at most three times. Here, we improve previous upper bounds for (n,3)-MAXSAT in terms of n (number of variables) and in terms of k (number of clauses that we are required to satisfy). Moreover, we prove that satisfying more clauses than the simple all true assignment is an NP-hard problem.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Exact Computation of Strongly Connected Reliability by Binary Decision Diagrams

Alon, N., Gutin, G., Kim, E.J., Szeider, S., Yeo, A.: Solving MAX-r-SAT above a tight lower bound. Algorithmica 61(3), 638–655 (2011)MathSciNetCrossRef

Bansal, N., Raman, V.: Upper bounds for MaxSat: further improved. ISAAC 1999. LNCS, vol. 1741, pp. 247–258. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-46632-0_26CrossRef

Basavaraju, M., Francis, M.C., Ramanujan, M., Saurabh, S.: Partially polynomial kernels for set cover and test cover. SIAM J. Discrete Math. 30(3), 1401–1423 (2016)MathSciNetCrossRef

Battiti, R., Protasi, M.: Reactive search, a history-sensitive heuristic for MAX-SAT. J. Exp. Algorithmics (JEA) 2, 2 (1997)MathSciNetCrossRef

Berg, J., Hyttinen, A., Järvisalo, M.: Applications of MaxSAT in data analysis. Pragmatics of SAT (2015)

Bliznets, I., Golovnev, A.: A new algorithm for parameterized MAX-SAT. In: Thilikos, D.M., Woeginger, G.J. (eds.) IPEC 2012. LNCS, vol. 7535, pp. 37–48. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-33293-7_6CrossRefMATH

Bliznets, I.A.: A new upper bound for (n, 3)-MAX-SAT. J. Math. Sci. 188(1), 1–6 (2013)MathSciNetCrossRef

Chen, J., Kanj, I.A.: Improved exact algorithms for MAX-SAT. Discrete Appl. Math. 142(1–3), 17–27 (2004)MathSciNetCrossRef

Chen, J., Xu, C., Wang, J.: Dealing with 4-variables by resolution: an improved MaxSAT algorithm. In: Dehne, F., Sack, J.-R., Stege, U. (eds.) WADS 2015. LNCS, vol. 9214, pp. 178–188. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-21840-3_15CrossRef

10.

Crowston, R., Gutin, G., Jones, M., Raman, V., Saurabh, S., Yeo, A.: Fixed-parameter tractability of satisfying beyond the number of variables. Algorithmica 68(3), 739–757 (2014)MathSciNetCrossRef

11.

Crowston, R., Jones, M., Mnich, M.: Max-Cut parameterized above the edwards-erdős bound. Algorithmica 72(3), 734–757 (2015)MathSciNetCrossRef

12.

Fomin, F.V., Kratsch, D.: Exact Exponential Algorithms. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-16533-7CrossRefMATH

13.

Gutin, G., Kim, E.J., Lampis, M., Mitsou, V.: Vertex cover problem parameterized above and below tight bounds. Theory Comput. Syst. 48(2), 402–410 (2011)MathSciNetCrossRef

14.

Gutin, G., Rafiey, A., Szeider, S., Yeo, A.: The linear arrangement problem parameterized above guaranteed value. Theory Comput. Syst. 41(3), 521–538 (2007)MathSciNetCrossRef

15.

Kojevnikov, A., Kulikov, A.S.: A new approach to proving upper bounds for MAX-2-SAT. In: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm, pp. 11–17. Society for Industrial and Applied Mathematics (2006)

16.

Kulikov, A.S., Kutskov, K.: New upper bounds for the problem of maximal satisfiability. Discrete Math. Appl. 19(2), 155–172 (2009)MathSciNetCrossRef

17.

Li, W., Xu, C., Wang, J., Yang, Y.: An improved branching algorithm for (n, 3)-MaxSAT based on refined observations. In: Gao, X., Du, H., Han, M. (eds.) COCOA 2017 Part II. LNCS, vol. 10628, pp. 94–108. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-71147-8_7CrossRef

18.

Lin, P.C.K., Khatri, S.P.: Application of MAX-SAT-based atpg to optimal cancer therapy design. BMC Genomics 13(6), S5 (2012)CrossRef

19.

Madathil, J., Saurabh, S., Zehavi, M.: Max-Cut Above Spanning Tree is fixed-parameter tractable. In: Fomin, F.V., Podolskii, V.V. (eds.) CSR 2018. LNCS, vol. 10846, pp. 244–256. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-90530-3_21CrossRef

20.

Mahajan, M., Raman, V.: Parameterizing above guaranteed values: MaxSat and MaxCut. J. Algorithms 31(2), 335–354 (1999)MathSciNetCrossRef

21.

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

22.

Poloczek, M., Schnitger, G., Williamson, D.P., Van Zuylen, A.: Greedy algorithms for the maximum satisfiability problem: simple algorithms and inapproximability bounds. SIAM J. Comput. 46(3), 1029–1061 (2017)MathSciNetCrossRef

23.

Raman, V., Ravikumar, B., Rao, S.S.: A simplified NP-complete MAXSAT problem. Inf. Processing Letters 65(1), 1–6 (1998)MathSciNetCrossRef

24.

Walter, R., Zengler, C., Küchlin, W.: Applications of MAXSAT in automotive configuration. In: Configuration Workshop, vol. 1, p. 21 (2013)

25.

Xu, C., Chen, J., Wang, J.: Resolution and linear CNF formulas: improved (n, 3)-MaxSAT algorithms. Theor. Comput. Sci. (2016)

Title: Upper and Lower Bounds for Different Parameterizations of (n,3)-MAXSAT
Authors: Tatiana Belova
Ivan Bliznets
Publisher: Springer International Publishing
Book: Combinatorial Optimization and Applications
Print ISBN: 978-3-030-04650-7

Electronic ISBN: 978-3-030-04651-4

Copyright Year: 2018
DOI: https://doi.org/10.1007/978-3-030-04651-4_20

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner