Covering points with axis parallel lines
| dc.contributor.author | Jahan, Kawsar | |
| dc.contributor.author | University of Lethbridge. Faculty of Arts and Science | |
| dc.contributor.supervisor | Gaur, Daya | |
| dc.contributor.supervisor | Benkoczi, Robert | |
| dc.date.accessioned | 2016-02-12T23:11:43Z | |
| dc.date.available | 2016-02-12T23:11:43Z | |
| dc.date.issued | 2015 | |
| dc.degree.level | Masters | en_US |
| dc.description.abstract | In this thesis, we study the problem of covering points with axis parallel lines. We named it as the point cover problem. Given a set of the n points in d dimensional space, the goal is to cover the points with minimum number of axis parallel lines. We use the iterative rounding approach which gives an integral solution to the problem. We also propose a combinatorial algorithm by using the branch and bound technique which gives an optimal integral solution to the point cover problem. Later we implemented another approximation algorithm based on primal-dual and iterative rounding approaches. Finally we show the comparative analysis between the two iterative rounding algorithms. | en_US |
| dc.embargo | No | en_US |
| dc.identifier.uri | https://hdl.handle.net/10133/4414 | |
| dc.language.iso | en_CA | en_US |
| dc.proquest.subject | 0984 | en_US |
| dc.proquestyes | Yes | en_US |
| dc.publisher | Lethbridge, Alta : University of Lethbridge, Dept. of Mathematics and Computer Science | en_US |
| dc.publisher.department | Department of Mathematics and Computer Science | en_US |
| dc.publisher.faculty | Arts and Science | en_US |
| dc.relation.ispartofseries | Thesis (University of Lethbridge. Faculty of Arts and Science) | en_US |
| dc.subject | 3 dimensional space | en_US |
| dc.subject | axis parallel lines | en_US |
| dc.subject | branch and bound | en_US |
| dc.subject | covering points | en_US |
| dc.title | Covering points with axis parallel lines | en_US |
| dc.type | Thesis | en_US |