Groupe

GT

Les GT se tiennent chaque vendredi de 14h à 15h (d'ordinaire en salle 178, ils se sont dématérialisés jusqu'à nouvel ordre). Vous êtes invités à venir 10 minutes avant pour partager thé, café et gâteaux.

Pour vous inscrire à la liste de diffusion, il suffit d'envoyer un mail à sympa@diff.u-bordeaux.fr avec pour sujet "subscribe labri.go-gt Cookie Monster", où Cookie est remplacé par votre prénom et Monster par votre nom.

Voir l'agenda des GT: webmel.u-bordeaux.fr/service/user/bf-labri.go@u-bordeaux.fr/gt.html https://webmel.u-bordeaux.fr/home/bf-labri.ca@u-bordeaux.fr/gt.go.html; pour l'ajouter au vôtre, webmel.u-bordeaux.fr/service/user/bf-labri.go@u-bordeaux.fr/gt.ics https://webmel.u-bordeaux.fr/home/bf-labri.ca@u-bordeaux.fr/gt.go.ics ou bien flasher le QRCode suivant:

Prochains exposés :

Les exposés en ligne sont accessibles à cette adresse : https://webconf.u-bordeaux.fr/b/mar-ef4-zed.

Vendredi 21 Juin à 14h - Nicolas Bonichon
Freeze-Tag in $L_1$ has Wake-up Time Five with Linear Complexity
The Freeze-Tag Problem, introduced in Arkin et al. (SODA'02) consists of waking up a swarm of n robots, starting from a single active robot. In the basic geometric version, every robot is given coordinates in the plane. As soon as a robot is awakened, it can move towards inactive robots to wake them up. The goal is to minimize the makespan of the last robot, the makespan.

Despite significant progress on the computational complexity of this problem and on approximation algorithms, the characterization of exact bounds on the makespan remains one of the main open questions. In this paper, we settle this question for the $\ell_1$-norm, showing that a makespan of at most 5r can always be achieved, where r is the maximum distance between the initial active robot and any sleeping robot. Moreover, a schedule achieving a makespan of at most 5r can be computed in time O(n). Both bounds, the time and the makespan are optimal. Our results also imply for the $\ell_2$-norm a new upper bound of 5√2r ≈ 7.07r on the makespan, improving the best known bound of (5+2√2+√5)r ≈ 10.06r.

Along the way, we introduce new linear time wake-up strategies, that apply to any norm and show that an optimal bound on the makespan can always be achieved by a schedule computable in linear time.

Emplois - Stages

Groupe

GT Graphes et Optimisation

Historique

edit SideBar

Blix theme adapted by David Gilbert, powered by PmWiki