University of Twente Student Theses
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.
|
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: | https://purl.utwente.nl/essays/82371 |
| Export this item as: | BibTeX EndNote HTML Citation Reference Manager |
Show download statistics for this publication
Show download statistics for this publicationRepository Staff Only: item control page