SCHOOL OF COMPUTER SCIENCE
The School of Computer Science at the University of Windsor is pleased to present …
VARIATIONS IN GREEDY APPROACH TO SET COVERING PROBLEM
MSc Thesis Defense by:
Shreeya Singhania
Date: Monday, April 8th, 2019
Time: 10:00 am – 12:00 pm
Location: 3105, Lambton Tower
Abstract:
The weighted set covering problem is to choose a number of subsets to cover all the elements in a universal set at the lowest cost. It is a well-studied classical problem with applications in various fields like machine learning, planning, information retrieval, facility allocation, etc. Deep web crawling refers to the process of gathering documents that have been structured into a data source and can be retrieved through a search interface. Its query selection process calls for an efficient solution to the weighted set covering problem. Within this context, the data follows the lognormal and power law distribution, and a TS-IDS algorithm has been proposed in the literature and demonstrated to outperform both the greedy and the IDS algorithm. We have evaluated the performance of various greedy approaches to the set covering problem, including the TS-IDS, using open source dataset in the context of resource management. The data are sampled from a given roadmap with different coverage radius.
Thesis Committee:
Thesis Defense Announcement