Sharma_Preeti.pdf (5.85 MB)
Download file

Worst-case & average-case Efficiency trade-offs for search problems

Download (5.85 MB)
thesis
posted on 24.05.2021, 12:14 authored by Preeti Sharma
Evacuation 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

eng

Degree

Master of Applied Science

Program

Applied Mathematics

Granting Institution

Ryerson University

LAC Thesis Type

Thesis

Usage metrics

Keywords

Exports