Top

Published in:

2020 | OriginalPaper | Chapter

On the Minimum Satisfiability Problem

Authors : Umair Arif, Robert Benkoczi, Daya Ram Gaur, Ramesh Krishnamurti

Published in: Algorithms and Discrete Applied Mathematics

Publisher: Springer International Publishing

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

search-config

AI-assisted search

Off

Abstract

We characterize the optimal solution to the LP relaxation of the standard formulation for the minimum satisfiability problem. Based on the characterization, we give a \(O(nm^2)\) combinatorial algorithm to solve the fractional version of the minimum satisfiability problem optimally where n(m) is the number of variables (clauses). As a by-product, we obtain a \(2(1-1/2^k)\) approximation algorithm for the minimum satisfiability problem where k is the maximum number of literals in any clause. We also give a simple linear time 2 approximation algorithm.

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 The Relative Oriented Clique Number of Triangle-Free Planar Graphs Is 10

next chapter Waiting for Trains: Complexity Results

Arif, U.M.: On primal-dual schema for the minimum satisfiability problem. Master’s thesis, University of Lethbridge, Canada (2017)

Bar-Yehuda, R., Even, S.: A linear-time approximation algorithm for the weighted vertex cover problem. J. Algorithms 2(2), 198–203 (1981). ISSN 0196–6774MathSciNetMATHCrossRef

Bar-Yehuda, R., Even, S.: A local-ratio theorem for approximating the weighted vertex cover problem. North-Holland Math. Stud. 109, 27–45 (1985)MathSciNetMATHCrossRef

Berman, P., Fujito, T.: On approximation properties of the independent set problem for low degree graphs. Theory Comput. Syst. 32(2), 115–132 (1999)MathSciNetMATHCrossRef

Bertsimas, D., Teo, C., Vohra, R.: On dependent randomized rounding algorithms. Oper. Res. Lett. 24(3), 105–114 (1999)MathSciNetMATHCrossRef

Bourjolly, J.-M., Pulleyblank, W.R.: König-Everváry graphs, 2-bicritical graphs and fractional matchings. Discrete Appl. Math. 24(1–3), 63–82 (1989)MathSciNetMATHCrossRef

Cook, S.A.: The complexity of theorem-proving procedures. In: Proceedings of the Third Annual ACM Symposium on Theory of Computing, STOC 1971, pp. 151–158, New York, NY, USA. ACM (1971)

Dinur, I., Safra, S.: On the hardness of approximating minimum vertex cover. Ann. Math. 162, 439–485 (2005) MathSciNetMATHCrossRef

Edmonds, J.: Paths, trees, and flowers. Can. J. Math. 17(3), 449–467 (1965)MathSciNetMATHCrossRef

Goemans, M.X., Williamson, D.P.: New \(\frac{3}{4}\)-approximation algorithms for the maximum satisfiability problem. SIAM J. Discrete Math. 7(4), 656–666 (1994)MathSciNetMATHCrossRef

Halperin, E.: Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs. SIAM J. Comput. 31(5), 1608–1623 (2002)MathSciNetMATHCrossRef

Hochbaum, D.S.: Instant recognition of half integrality and 2-approximations. In: Jansen, K., Rolim, J. (eds.) APPROX 1998. LNCS, vol. 1444, pp. 99–110. Springer, Heidelberg (1998). https://doi.org/10.1007/BFb0053967CrossRef

Hochbaum, D.S.: Approximation algorithms for the set covering and vertex cover problems. SIAM J. Comput. 11(3), 555–556 (1982)MathSciNetMATHCrossRef

Hochbaum, D.S.: Efficient bounds for the stable set, vertex cover and set packing problems. Discrete Appl. Math. 6(3), 243–254 (1983)MathSciNetMATHCrossRef

Iranmanesh, E.: Algorithms for Problems in Voting and Scheduling. Ph.D. thesis, Simon Fraser University (2016)

Johnson, D.S.: Approximation algorithms for combinatorial problems. J. Comput. Syst. Sci. 9(3), 256–278 (1974)MathSciNetMATHCrossRef

Khot, S., Regev, O.: Vertex cover might be hard to approximate to within \(2- \varepsilon \). J. Comput. Syst. Sci. 74(3), 335–349 (2008)MathSciNetMATHCrossRef

Kohli, R., Krishnamurti, R., Mirchandani, P.: The minimum satisfiability problem. SIAM J. Discret. Math. 7(2), 275–283 (1994)MathSciNetMATHCrossRef

Krishnamurti, R., Gaur, D.R., Ghosh, S.K., Sachs, H.: Berge’s theorem for the maximum charge problem. Discrete Optim. 3(2), 174–178 (2006)MathSciNetMATHCrossRef

Marathe, M., Ravi, S.: On approximation algorithms for the minimum satisfiability problem. Inf. Process. Lett. 58(1), 23–29 (1996)MathSciNetMATHCrossRef

Monien, B., Speckenmeyer, E.: Ramsey numbers and an approximation algorithm for the vertex cover problem. Acta Informatica 22(1), 115–123 (1985)MathSciNetMATHCrossRef

Orlin, J.B.: Max flows in O(nm) time, or better. In: Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, pp. 765–774. ACM (2013)

Papadimitriou, C.H., Steiglitz, K.: Combinatorial Optimization: Algorithms and Complexity. Courier Corporation, North Chelmsford (1982) MATH

Tardos, E.: A strongly polynomial algorithm to solve combinatorial linear programs. Oper. Res. 34(2), 250–256 (1986)MathSciNetMATHCrossRef

Yannakakis, M.: On the approximation of maximum satisfiability. In: Proceedings of the Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1992, pp. 1–9, Philadelphia, PA, USA (1992). ISBN 0-89791-466-X

Title: On the Minimum Satisfiability Problem
Authors: Umair Arif
Robert Benkoczi
Daya Ram Gaur
Ramesh Krishnamurti
Publisher: Springer International Publishing
Book: Algorithms and Discrete Applied Mathematics
Print ISBN: 978-3-030-39218-5

Electronic ISBN: 978-3-030-39219-2

Copyright Year: 2020
DOI: https://doi.org/10.1007/978-3-030-39219-2_23

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