Solving NP-hard facility location problems in wireless network planning is a common scenario.
In our research, we study the Covering problem, a well known facility location problem with applications
in wireless network deployment. We focus on networks with a sparse structure. First,
we analyzed two heuristics of building Tree Decomposition based on vertex separator and perfect
elimination order. We extended the vertex separator heuristic to improve its time performance. Second,
we propose a dynamic programming algorithm based on the Tree Decomposition to solve the
Covering problem optimally on the network. We developed several heuristic techniques to speed
up the algorithm. Experiment results show that one variant of the dynamic programming algorithm
surpasses the performance of the state of the art mathematical optimization commercial software on
several occasions. / ix, 89 leaves : ill. ; 29 cm
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:ALU.w.uleth.ca/dspace#10133/3235 |
| Date | January 2011 |
| Creators | Sabbir, Tarikul Alam Khan |
| Contributors | Gaur, Daya, Benkoczi, Robert |
| Publisher | Lethbridge, Alta. : University of Lethbridge, Dept. of Mathematics and Computer Science, c2011, Arts and Science, Department of Mathematics and Computer Science |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | en_US |
| Detected Language | English |
| Type | Thesis |
| Relation | Thesis (University of Lethbridge. Faculty of Arts and Science) |
Page generated in 0.0022 seconds