University of Twente Student Theses

Login

Finding lower bounds for the competitive ratio of the cow path problem with a non-optimal seeker.

Vos, M.C. (2020) Finding lower bounds for the competitive ratio of the cow path problem with a non-optimal seeker.

[img] PDF
920kB
Abstract:A tight lower bound for the competitive ratio of deterministic algorithms for the cow path is well-known. In this thesis, we generalize the cow path problem by assuming that the seeker finds the hider after some known number of visits. We seek to find lower bounds for the competitive ratio of deterministic algorithms for this problem. The thesis describes the general form of optimal algorithms and succeeds in finding a tight lower bound for the competitive ratio when the required number of visits is odd.
Item Type:Essay (Bachelor)
Faculty:EEMCS: Electrical Engineering, Mathematics and Computer Science
Subject:31 mathematics, 54 computer science
Programme:Applied Mathematics BSc (56965)
Link to this item:http://purl.utwente.nl/essays/82371
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page