{"id":{"repo_id":"lethbridge","oai_identifier":"oai:opus.uleth.ca:10133/4983"},"canonical_url":"https://search.dev.ndltd.org/etd/lethbridge/oai:opus.uleth.ca:10133/4983","repository":{"repo_id":"lethbridge","name":"University of Lethbridge","base_url":"https://opus.uleth.ca/server/oai/request"},"display":{"title":"Point cover problem in 3D","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.","abstract_html":"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.","abstract_has_math":false,"creators":["Akter, Sharmin","University of Lethbridge. Faculty of Arts and Science"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2017,"date_issued":"2017","date_published":"2017","updated_at":"2026-07-27T20:02:32Z","subjects":["three dimensional space","points","axis parallel lines","Lagrangian relaxation","subgradient optimisation","lift-and-project","primal-dual","iterative","branch-and-bound","NVBLAS"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["hdl:10133/4983"],"render_values":[{"text":"hdl:10133/4983","href":null,"code":true}]}]},"links":{"outbound_url":null,"outbound_label":null,"outbound_source":null},"metadata_groups":[{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.issued","label":"Date","values":["2017"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["three dimensional space","points","axis parallel lines","Lagrangian relaxation","subgradient optimisation","lift-and-project","primal-dual","iterative","branch-and-bound","NVBLAS"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["hdl:10133/4983"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.other","label":"Dc Description Other","values":["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."]},{"key":"dc:title","label":"Title","values":["Point cover problem in 3D"]}]}],"canonical_facts":{"dc:date.issued":["2017"],"dc:description.other":["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."],"dc:identifier":["hdl:10133/4983"],"dc:subject":["three dimensional space","points","axis parallel lines","Lagrangian relaxation","subgradient optimisation","lift-and-project","primal-dual","iterative","branch-and-bound","NVBLAS"],"dc:title":["Point cover problem in 3D"],"dc:type":["Thesis"]},"updated_at":"2026-07-27T20:02:32Z"}