Sharma_Preeti.pdf (5.85 MB)
Download fileWorst-case & average-case Efficiency trade-offs for search problems
thesis
posted on 2021-05-24, 12:14 authored by Preeti SharmaEvacuation problems fall under the vast area of search theory and operations research. Problems of evacuation of two robots on a unit disc have been studied for an efficient evacuation time. Work done so far has focused on improving the ’worst-case’ evacuation time with deterministic algorithms. We study the ’average-case’ evacuation time (randomized algorithms) while considering the efficiency trade-off between worst-case and average-case costs. Our other contribution is to analyze
average-case and worst-case costs for the cowpath problem (another search problem) which helped us to set a parallel method for the evacuation problem.
History
Language
engDegree
- Master of Applied Science
Program
- Applied Mathematics
Granting Institution
Ryerson UniversityLAC Thesis Type
- Thesis