Topology sensitive algorithms for large scale uncapacitated covering problem

Simple item page
dc.contributor.authorSabbir, Tarikul Alam Khan
dc.contributor.supervisorGaur, Daya
dc.contributor.supervisorBenkoczi, Robert
dc.date.accessioned2013-01-18T18:26:14Z
dc.date.available2013-01-18T18:26:14Z
dc.date.issued2011
dc.degree.levelMasters
dc.descriptionix, 89 leaves : ill. ; 29 cmen_US
dc.description.abstractSolving 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.en_US
dc.identifier.urihttps://hdl.handle.net/10133/3235
dc.language.isoen_USen_US
dc.publisherLethbridge, Alta. : University of Lethbridge, Dept. of Mathematics and Computer Science, c2011en_US
dc.publisher.departmentDepartment of Mathematics and Computer Scienceen_US
dc.publisher.facultyArts and Scienceen_US
dc.relation.ispartofseriesThesis (University of Lethbridge. Faculty of Arts and Science)en_US
dc.subjectCombinatorial optimizationen_US
dc.subjectTrees (Graph theory)en_US
dc.subjectAlgorithmsen_US
dc.subjectWireless interneten_US
dc.subjectWireless sensor networksen_US
dc.subjectDissertations, Academicen_US
dc.titleTopology sensitive algorithms for large scale uncapacitated covering problemen_US
dc.typeThesisen_US
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
SABBIR_TARIKUL_MSC_2011.pdf
Size:
733.48 KB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
1.63 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Arts and Science, Faculty of
University of Lethbridge Theses