Ομιλητής: Ευάγγελος Κρανάκης (School of Computer Science, Carleton University)
Τίτλος: Impact of Knowledge on the Competitive Ratio of Linear Search
Ημερομηνία: Τρίτη 25/2, ώρα 18:15-19:30
Αίθουσα: 1.31, Παλ. Κτ. Ηλεκτρολόγων ΕΜΠ
Σύνοψη:
We give a survey of recent results and propose open problems in linear search by searchers, modelled as autonomous mobile agents. The trajectories of the searchers are continuous and the search domain is the infinite real line or generalizations thereof. The design of the algorithms takes into account the impact of the knowledge the searchers have about the communication model and the faulty behaviour of searchers in order to obtain an optimal competitive ratio. The approach emphasizes agent co-operation and distributed algorithm design principles. Goal is to understand the impact of knowledge on the competitive ratio of linear search.