Date of Award
2018
Publication Type
Master Thesis
Degree Name
M.Sc.
Department
Computer Science
Keywords
big data; set covering algorithms
Supervisor
Chen, Jessica
Rights
info:eu-repo/semantics/openAccess
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Abstract
Set covering is a well-studied classical problem with many applications across different fields. More recent work on this problem has taken into account the parallel computing architecture, the datasets at scale, the properties of the datasets, etc. Within the context of web crawling where the data follow the lognormal distribution, a weighted greedy algorithm has been proposed in the literature and demonstrated to outperform the traditional one. In the present work, we evaluate the performance of the weighted greedy algorithm using an open-source dataset in the context of resource management. The data are sampled from a given roadmap with 1.9 millions of nodes. Our research includes three different cost definitions i.e. location cost, driving cost and infrastructure cost. We also consider the different coverage radius to model possible parameters in the application. Our experiment results show that weighted greedy algorithm outperforms the greedy algorithm by 8% in average for all three different cost definitions.
Recommended Citation
Singh, Harjeet, "Performance Evaluation of Weighted Greedy Algorithm in Resource Management" (2018). Electronic Theses and Dissertations. 7397.
https://scholar.uwindsor.ca/etd/7397