Show simple item record

dc.contributor.supervisor Gaur, Daya
dc.contributor.author Akter, Sharmin
dc.contributor.author University of Lethbridge. Faculty of Arts and Science
dc.date.accessioned 2017-11-21T17:55:31Z
dc.date.available 2017-11-21T17:55:31Z
dc.date.issued 2017
dc.identifier.uri https://hdl.handle.net/10133/4983
dc.description.abstract We 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.language.iso en_US en_US
dc.publisher Lethbridge, Alta. : Universtiy of Lethbridge, Department of Mathematics and Computer Science en_US
dc.relation.ispartofseries Thesis (University of Lethbridge. Faculty of Arts and Science) en_US
dc.subject three dimensional space en_US
dc.subject points en_US
dc.subject axis parallel lines en_US
dc.subject Lagrangian relaxation en_US
dc.subject subgradient optimisation en_US
dc.subject lift-and-project en_US
dc.subject primal-dual en_US
dc.subject iterative en_US
dc.subject branch-and-bound en_US
dc.subject NVBLAS en_US
dc.title Point cover problem in 3D en_US
dc.type Thesis en_US
dc.publisher.faculty Arts and Science en_US
dc.publisher.department Department of Mathematics and Computer Science en_US
dc.degree.level Masters en_US
dc.proquest.subject 0984 en_US
dc.proquestyes Yes en_US
dc.embargo No en_US


Files in this item

This item appears in the following Collection(s)

Show simple item record