Back to search

Lethbridge, Alta : University of Lethbridge, Dept. of Mathematics and Computer Science

On primal-dual schema for the minimum satisfiability problem

Abstract

dc:description.abstract

Satisfiability problem is the first problem known to be NP-complete [8, 28]. In this thesis, we have studied the minimization version of the satisfiability problem called the MINSAT. Given a set of boolean variables and a set of clauses, such that each clause is a disjunction of variables, the goal is to find the boolean values of the variables so that minimum number of clauses are satisfied. We have used the concept of linear programming and the primal-dual method to study the problem. We have constructed the Linear program of the MINSAT and its restricted version. We have proposed two combinatorial methods to solve the dual of the restricted primal of the MINSAT. Further to this, these two algorithms also obtain an integral solution to the dual of the MINSAT problem. Lastly, we performed a comparison analysis of our proposed algorithms with the simplex method.

Degree

thesis:*
Level thesis:degree_level
Masters
Grantor dc:publisher
Lethbridge, Alta : University of Lethbridge, Dept. of Mathematics and Computer Science
Year dc:date.issued
2016

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Muhammad Arif, Umair
  • University of Lethbridge. Faculty of Arts and Science
Advisors dc:contributor.supervisor
  • Gaur, Daya
  • Benkoczi, Robert

Subjects

dc:subject × 4

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/10133/4765

Chain of custody

source
Harvested from
University of Lethbridge
Base URL
opus.uleth.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Muhammad Arif, Umair; University of Lethbridge. Faculty of Arts and Science. On primal-dual schema for the minimum satisfiability problem. Masters thesis, Lethbridge, Alta : University of Lethbridge, Dept. of Mathematics and Computer Science, 2016. https://hdl.handle.net/10133/4765