nach oben

Journal of Combinatorial Optimization

Erschienen in:

17.05.2019

An improved algorithm for the \((n, 3)\)-MaxSAT problem: asking branchings to satisfy the clauses

verfasst von: Chao Xu, Wenjun Li, Jianxin Wang, Yongjie Yang

Erschienen in: Journal of Combinatorial Optimization | Ausgabe 3/2021

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We study the \((n, 3)\)-MaxSAT problem where we are given an integer k and a CNF formula with n variables, each of which appears in at most 3 clauses, and the question is whether there is an assignment that satisfies at least k clauses. Based on refined observations, we propose a branching algorithm for the \((n, 3)\)-MaxSAT problem which significantly improves the previous results. More precisely, the running time of our algorithm can be bounded by \(O^*(1.175^k)\) and \(O^*(1.194^n)\), respectively. Prior to our study, the running time of the best known exact algorithm can be bounded by \(O^*(1.194^k)\) and \(O^*(1.237^n)\), respectively.

Vorheriger Artikel Algorithms for the metric ring star problem with fixed edge-cost ratio

Nächster Artikel Batch scheduling of nonidentical job sizes with minsum criteria

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Argelich J, Manyà F (2006) Exact Max-SAT solvers for over-constrained problems. J Heuristics 12(4–5):375–392CrossRef

Aspvall B, Plass MF, Tarjan RE (1979) A linear-time algorithm for testing the truth of certain quantified boolean formulas. Inf Process Lett 8(3):121–123MathSciNetCrossRef

Bansal N, Raman V (1999) Upper bounds for MaxSAT: further improved. In: ISAAC, pp 247–258

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

Bliznets I, Golovnev A (2012) A new algorithm for parameterized MAX-SAT. In: IPEC, pp 37–48

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

Bonet ML, Levy J, Manyà F (2007) Resolution for Max-SAT. Artif Intell 171(8–9):606–618MathSciNetCrossRef

Calabro C, Impagliazzo R, Paturi R (2006) A duality between clause width and clause density for SAT. In: CCC, pp 252–260

Chen J, Kanj IA (2004) Improved exact algorithms for Max-Sat. Discrete Appl Math 142(1–3):17–27MathSciNetCrossRef

Chen J, Kanj IA, Xia G (2010) Improved upper bounds for vertex cover. Theor Comput Sci 411(40–42):3736–3756MathSciNetCrossRef

Cook SA (1971) The complexity of theorem-proving procedures. In: STOC, pp 151–158

Cygan M, Fomin FV, Kowalik L, Lokshtanov D, Marx D, Pilipczuk M, Pilipczuk M, Saurabh S (2015) Lower bounds based on the exponential-time hypothesis. Springer, Berlin, pp 467–521

Fomin FV, Kratsch D (2010) Exact exponential algorithms, chapter 2. Texts in theoretical computer science An EATCS series. Springer, Berlin, pp 13–30CrossRef

Garey M, Johnson D (1979) Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman, New YorkMATH

Goemans MX, Williamson DP (1994) New 3/4-approximation algorithms for the maximum satisfiability problem. SIAM J Discrete Math 7(4):656–666MathSciNetCrossRef

Goemans MX, Williamson DP (1995) Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J ACM 42(6):1115–1145MathSciNetCrossRef

Gu J (1994) Global optimization for satisfiability (SAT) problem. IEEE Trans Knowl Data Eng 6(3):361–381CrossRef

Hirsch EA (2000) New worst-case upper bounds for SAT. J Autom Reason 24(4):397–420MathSciNetCrossRef

Hirsch EA, Kojevnikov A (2005) Unitwalk: a new SAT solver that uses local search guided by unit clause elimination. Ann Math Artif Intell 43(1):91–111MathSciNetCrossRef

Hochbaum D (1997) Approximation algorithms for NP-hard problems. PWS Publishing Company, BostonMATH

Hutter F, Lindauer M, Balint A, Bayless S, Hoos H, Leyton-Brown K (2017) The configurable SAT solver challenge (CSSC). Artif Intell 243:1–25MathSciNetCrossRef

Impagliazzo R, Paturi R (2001) On the complexity of \(k\)-SAT. J Comput Syst Sci 62(2):367–375MathSciNetCrossRef

Karloff HJ, Zwick U (1997) A 7/8-approximation algorithm for MAX 3SAT? In: FOCS, pp 406–415

Kulikov AS (2005) Automated generation of simplification rules for SAT and MAXSAT. In: SAT, pp 430–436

Li W, Xu C, Wang J, Yang Y (2017) An improved branching algorithm for \((n, 3)\)-MaxSAT based on refined observations. In: COCOA, pp 94–108

Lokshtanov D (2009) New methods in parameterized algorithms and complexity. Ph.D. thesis, University of Bergen

Luo C, Cai S, Su K, Huang W (2017) CCEHC: an efficient local search algorithm for weighted partial maximum satisfiability. Artif Intell 243:26–44MathSciNetCrossRef

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

Patrascu M, Williams R (2010) On the possibility of faster SAT algorithms. In: SODA, pp 1065–1075

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

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

Saikko P, Malone B, Järvisalo M (2015) MaxSAT-based cutting planes for learning graphical models. In: CPAIOR, pp 347–356

Selman B, Mitchell DG, Levesque HJ (1996) Generating hard satisfiability problems. Artif Intell 81(1–2):17–29MathSciNetCrossRef

Shen H, Zhang H (2005) Improving exact algorithms for MAX-2-SAT. Ann Math Artif Intell 44(4):419–436MathSciNetCrossRef

Xiao M, Nagamochi H (2016) An exact algorithm for maximum independent set in degree-5 graphs. Discrete Appl Math 199:137–155MathSciNetCrossRef

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

Titel: An improved algorithm for the -MaxSAT problem: asking branchings to satisfy the clauses
verfasst von: Chao Xu
Wenjun Li
Jianxin Wang
Yongjie Yang
Publikationsdatum: 17.05.2019
Verlag: Springer US
Erschienen in: Journal of Combinatorial Optimization / Ausgabe 3/2021
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-019-00421-1

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 3/2021

A spectral partitioning algorithm for maximum directed cut problem

Conflict-free connection of trees

An improved mechanism for selfish bin packing

A dynamic approach to detecting, eliminating and fixing memory leaks

On the complexity and approximability of repair position selection problem

Tropical paths in vertex-colored graphs

Premium Partner