Back to search

Lethbridge, Alta. : Universtiy of Lethbridge, Department of Mathematics and Computer Science

Point cover problem in 3D

Abstract

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.

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 × 10

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/10133/4983

Chain of custody

source
Harvested from
University of Lethbridge
Base URL
opus.uleth.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Akter, Sharmin; University of Lethbridge. Faculty of Arts and Science. Point cover problem in 3D. Masters thesis, Lethbridge, Alta. : Universtiy of Lethbridge, Department of Mathematics and Computer Science, 2017. https://hdl.handle.net/10133/4983