Skip to main content

2020 | OriginalPaper | Buchkapitel

On the Minimum Satisfiability Problem

verfasst von : Umair Arif, Robert Benkoczi, Daya Ram Gaur, Ramesh Krishnamurti

Erschienen in: Algorithms and Discrete Applied Mathematics

Verlag: Springer International Publishing

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

search-config
loading …

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.

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!

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!

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!

Literatur
Zurück zum Zitat Arif, U.M.: On primal-dual schema for the minimum satisfiability problem. Master’s thesis, University of Lethbridge, Canada (2017) Arif, U.M.: On primal-dual schema for the minimum satisfiability problem. Master’s thesis, University of Lethbridge, Canada (2017)
Zurück zum Zitat 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 linear-time approximation algorithm for the weighted vertex cover problem. J. Algorithms 2(2), 198–203 (1981). ISSN 0196–6774MathSciNetMATHCrossRef
Zurück zum Zitat 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 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
Zurück zum Zitat 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 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
Zurück zum Zitat 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 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
Zurück zum Zitat 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) 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)
Zurück zum Zitat 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 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
Zurück zum Zitat Halperin, E.: Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs. SIAM J. Comput. 31(5), 1608–1623 (2002)MathSciNetMATHCrossRef Halperin, E.: Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs. SIAM J. Comput. 31(5), 1608–1623 (2002)MathSciNetMATHCrossRef
Zurück zum Zitat 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.: Approximation algorithms for the set covering and vertex cover problems. SIAM J. Comput. 11(3), 555–556 (1982)MathSciNetMATHCrossRef
Zurück zum Zitat Hochbaum, D.S.: Efficient bounds for the stable set, vertex cover and set packing problems. Discrete Appl. Math. 6(3), 243–254 (1983)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
Zurück zum Zitat Iranmanesh, E.: Algorithms for Problems in Voting and Scheduling. Ph.D. thesis, Simon Fraser University (2016) Iranmanesh, E.: Algorithms for Problems in Voting and Scheduling. Ph.D. thesis, Simon Fraser University (2016)
Zurück zum Zitat 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 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
Zurück zum Zitat Kohli, R., Krishnamurti, R., Mirchandani, P.: The minimum satisfiability problem. SIAM J. Discret. Math. 7(2), 275–283 (1994)MathSciNetMATHCrossRef Kohli, R., Krishnamurti, R., Mirchandani, P.: The minimum satisfiability problem. SIAM J. Discret. Math. 7(2), 275–283 (1994)MathSciNetMATHCrossRef
Zurück zum Zitat 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 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
Zurück zum Zitat Marathe, M., Ravi, S.: On approximation algorithms for the minimum satisfiability problem. Inf. Process. Lett. 58(1), 23–29 (1996)MathSciNetMATHCrossRef Marathe, M., Ravi, S.: On approximation algorithms for the minimum satisfiability problem. Inf. Process. Lett. 58(1), 23–29 (1996)MathSciNetMATHCrossRef
Zurück zum Zitat Monien, B., Speckenmeyer, E.: Ramsey numbers and an approximation algorithm for the vertex cover problem. Acta Informatica 22(1), 115–123 (1985)MathSciNetMATHCrossRef Monien, B., Speckenmeyer, E.: Ramsey numbers and an approximation algorithm for the vertex cover problem. Acta Informatica 22(1), 115–123 (1985)MathSciNetMATHCrossRef
Zurück zum Zitat 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) 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)
Zurück zum Zitat Papadimitriou, C.H., Steiglitz, K.: Combinatorial Optimization: Algorithms and Complexity. Courier Corporation, North Chelmsford (1982) MATH Papadimitriou, C.H., Steiglitz, K.: Combinatorial Optimization: Algorithms and Complexity. Courier Corporation, North Chelmsford (1982) MATH
Zurück zum Zitat 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 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
Metadaten
Titel
On the Minimum Satisfiability Problem
verfasst von
Umair Arif
Robert Benkoczi
Daya Ram Gaur
Ramesh Krishnamurti
Copyright-Jahr
2020
DOI
https://doi.org/10.1007/978-3-030-39219-2_23