BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//labri.fr//NONSGML kigkonsult.se iCalcreator 2.41.92//
CALSCALE:GREGORIAN
METHOD:PUBLISH
UID:c400362a-9e63-4af3-a9e9-798978b7f122
X-WR-CALNAME:[gt.go] - 'Freeze-Tag in $L_1$ has Wake-up Time Five with Line
 ar Complexity' by Nicolas Bonichon
X-WR-TIMEZONE:Europe/Paris
BEGIN:VTIMEZONE
TZID:Europe/Paris
TZUNTIL:20260329T010000Z
BEGIN:STANDARD
TZNAME:CET
DTSTART:20231029T030000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
RDATE:20241027T030000
RDATE:20251026T030000
END:STANDARD
BEGIN:DAYLIGHT
TZNAME:CEST
DTSTART:20240331T020000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
RDATE:20250330T020000
END:DAYLIGHT
END:VTIMEZONE
BEGIN:VEVENT
UID:c400362a-9e63-4af3-a9e9-798978b7f122
DTSTAMP:20260502T171355Z
CLASS:PUBLIC
DESCRIPTION:/Exposé /Talk/ \n\nThe Freeze-Tag Problem\, introduced in Arkin
  et al. (SODA'02) consists of waking up a swarm of /n/ robots\, starting f
 rom 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 m
 ove towards inactive robots to wake them up. The goal is to minimize the m
 akespan of the last robot\, the /makespan/. \n\nDespite significant progre
 ss on the computational complexity of this problem and on approximation al
 gorithms\, the characterization of exact bounds on the makespan remains on
 e 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 ro
 bot 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 th
 e 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/. \n\nAlong the way\, we introduce new line
 ar time wake-up strategies\, that apply to any norm and show that an optim
 al bound on the makespan can always be achieved by a schedule computable i
 n linear time. \n\n\n\n[Nicolas Bonichon ] (Université de Bordeaux\, LaBRI
  ) \nhttps://www.labri.fr/perso/bonichon/wiki/pmwiki.php \n\nRemarks / Rem
 arques \n\nFind all the information of the working group on this [ https:/
 /graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT?userlang=en | web pag
 e ] . \nRetrouvez toutes les informations du GT sur cette [ https://graphe
 setoptimisation.labri.fr/pmwiki.php/Groupe/GT | page web ] .
DTSTART;TZID=Europe/Paris:20240621T140000
DTEND;TZID=Europe/Paris:20240621T150000
LOCATION:LaBRI/178
SEQUENCE:0
SUMMARY:[gt.go] - 'Freeze-Tag in $L_1$ has Wake-up Time Five with Linear Co
 mplexity' by Nicolas Bonichon
TRANSP:OPAQUE
END:VEVENT
END:VCALENDAR
