Lethbridge, Alta. : Universtiy of Lethbridge, Department of Mathematics and Computer Science
Point cover problem in 3D
Abstract
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.
Degree
thesis:*- Level thesis:degree_level
- Masters
- Grantor dc:publisher
- Lethbridge, Alta. : Universtiy of Lethbridge, Department of Mathematics and Computer Science
- Year dc:date.issued
- 2017
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Akter, Sharmin
- University of Lethbridge. Faculty of Arts and Science
- Advisor dc:contributor.supervisor
-
- Gaur, Daya
Subjects
dc:subject × 10Rights
- Language dc:language.iso
- en_US
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- https://hdl.handle.net/10133/4983