On primal-dual schema for the minimum satisfiability problem

Simple item page
dc.contributor.authorMuhammad Arif, Umair
dc.contributor.authorUniversity of Lethbridge. Faculty of Arts and Science
dc.contributor.supervisorGaur, Daya
dc.contributor.supervisorBenkoczi, Robert
dc.date.accessioned2017-01-18T23:03:26Z
dc.date.available2017-01-18T23:03:26Z
dc.date.issued2016
dc.degree.levelMastersen_US
dc.description.abstractSatisfiability 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.en_US
dc.embargoNoen_US
dc.identifier.urihttps://hdl.handle.net/10133/4765
dc.language.isoen_USen_US
dc.proquest.subject0984en_US
dc.proquestyesYesen_US
dc.publisherLethbridge, Alta : University of Lethbridge, Dept. of Mathematics and Computer Scienceen_US
dc.publisher.departmentDepartment of Mathematics & Computer Scienceen_US
dc.publisher.facultyArts and Scienceen_US
dc.relation.ispartofseriesThesis (University of Lethbridge. Faculty of Arts and Science)en_US
dc.subjectintegral solutionen_US
dc.subjectlinear programmingen_US
dc.subjectMINSATen_US
dc.subjectprimal-dual methoden_US
dc.titleOn primal-dual schema for the minimum satisfiability problemen_US
dc.typeThesisen_US
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
ARIF_UMAIR_MSC_2016_v2.pdf
Size:
278.41 KB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
1.75 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Arts and Science, Faculty of
University of Lethbridge Theses