Actualités
  Période
semaine
ou mois
aucune période


  Thèmes:
Thèses
Colloques
Autres
Groupes
Tous les thèmes

   
  Liens:
Voir les thèses

Voir les colloques

Voir les autres événements

Voir la page des groupes

Accéder à l'intranet

Intitulé:   
Towards a General Framework for Searching on a Line and Searching on m Rays
du groupe Algorithmique Distribuée

Date 2014-12-01  14:00-15:00
TitreTowards a General Framework for Searching on a Line and Searching on m Rays 
RésuméWe revisit the problem of searching for a target at an unknown location on a line when given upper and lower bounds on the distance D that separates the initial position of the searcher from the target. We present tight bounds on the exact optimal competitive ratio achievable, parameterized in terms of the given range for D, along with an optimal search strategy that achieves this competitive ratio. We present an optimal search strategy for the case where a fixed turn cost t is charged every time the searcher changes direction. Moreover, we generalize our results to the framework where the cost of moving distance x away from the origin is a x + b and the cost of moving distance y towards the origin is c y + d for constants a, b, c and d. This is joint work with Prosenjit Bose (Carleton U.) and Stephane Durocher (U. of Manitoba). 
Lieu178 
OrateurJean-Lou De Carufel (Carleton University) 



Aucun document lié à cet événement.

Retour
Retour à l'index