Point cover problem in 3D

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.

Authors

• Akter, Sharmin
• University of Lethbridge. Faculty of Arts and Science

• three dimensional space
• points
• axis parallel lines
• Lagrangian relaxation
• subgradient optimisation
• lift-and-project
• primal-dual
• iterative
• branch-and-bound
• NVBLAS

Identifier

hdl:10133/4983

OAI identifier oai:identifier

oai:opus.uleth.ca:10133/4983