Point cover problem in 3D

Simple item page
dc.contributor.authorAkter, Sharmin
dc.contributor.authorUniversity of Lethbridge. Faculty of Arts and Science
dc.contributor.supervisorGaur, Daya
dc.date.accessioned2017-11-21T17:55:31Z
dc.date.available2017-11-21T17:55:31Z
dc.date.issued2017
dc.degree.levelMastersen_US
dc.description.abstractWe examine the problem of covering points with minimum number of axis-parallel lines in three dimensional space which is an NP-complete problem. We introduce Lagrangian based algorithms to approximate the point cover problem. We study the Lift-and-Project relaxation of the standard IP to obtain lower bounds. This method is used to strengthen the integrality gap of a problem. Our experimental results show that the Lagrangian relaxation method gives very good lower bounds at reasonable computational cost. We present a hybrid method where the Lift-and-Project LP is solved using the Subgradient Optimisation technique. We propose an approximation algorithm which iteratively uses the Lagrangian relaxation procedure. We also study a Branch-and-Bound method which gives an optimal solution. We use a drop-in accelerator while conducting the simulations on large instances.en_US
dc.embargoNoen_US
dc.identifier.urihttps://hdl.handle.net/10133/4983
dc.language.isoen_USen_US
dc.proquest.subject0984en_US
dc.proquestyesYesen_US
dc.publisherLethbridge, Alta. : Universtiy of Lethbridge, Department of Mathematics and Computer Scienceen_US
dc.publisher.departmentDepartment of Mathematics and Computer Scienceen_US
dc.publisher.facultyArts and Scienceen_US
dc.relation.ispartofseriesThesis (University of Lethbridge. Faculty of Arts and Science)en_US
dc.subjectthree dimensional spaceen_US
dc.subjectpointsen_US
dc.subjectaxis parallel linesen_US
dc.subjectLagrangian relaxationen_US
dc.subjectsubgradient optimisationen_US
dc.subjectlift-and-projecten_US
dc.subjectprimal-dualen_US
dc.subjectiterativeen_US
dc.subjectbranch-and-bounden_US
dc.subjectNVBLASen_US
dc.titlePoint cover problem in 3Den_US
dc.typeThesisen_US
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
AKTER_SHARMIN_MSC_2017.pdf
Size:
510.95 KB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
3.25 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Arts and Science, Faculty of
University of Lethbridge Theses