BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//labri.fr//NONSGML kigkonsult.se iCalcreator 2.41.92//
CALSCALE:GREGORIAN
METHOD:PUBLISH
UID:ef6b2d0b-ee4a-4c2a-84d5-46ab9026ea55
X-WR-CALNAME:GT AlgoDist\, «Graph Exploration with Edge Weight Estimates»\,
  Émile Naquin
X-WR-TIMEZONE:Europe/Paris
BEGIN:VTIMEZONE
TZID:Europe/Paris
TZUNTIL:20280326T010000Z
BEGIN:STANDARD
TZNAME:CET
DTSTART:20251026T030000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
RDATE:20261025T030000
RDATE:20271031T030000
END:STANDARD
BEGIN:DAYLIGHT
TZNAME:CEST
DTSTART:20260329T020000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
RDATE:20270328T020000
END:DAYLIGHT
END:VTIMEZONE
BEGIN:VEVENT
UID:ef6b2d0b-ee4a-4c2a-84d5-46ab9026ea55
DTSTAMP:20260610T103616Z
CLASS:PUBLIC
DESCRIPTION:Émile Naquin (LaBRI)\n\nTitle: Graph Exploration with Edge Weig
 ht Estimates\n\nAbstract:\n\nIn the Travelling Salesman Problem\, every ve
 rtex of an edge-weighted graph has to be visited by an agent who traverses
  the edges of the graph. In this problem\, it is usually assumed that the 
 costs of each edge are given in advance\, making it computationally hard b
 ut possible to calculate an optimal tour for the agent.\n\nAlso in the Gra
 ph Exploration Problem\, every vertex of a given graph must be visited\, b
 ut here the graph is not known in the beginning - at every point\, an algo
 rithm only knows about the already visited vertices and their neighbors.\n
 \nBoth however are not necessarily realistic settings: Usually the structu
 re of the graph (for example underlying road network) is known in advance\
 , but the details are not. One usually has a prediction of how long it tak
 es to traverse through a particular road\, but due to road conditions or i
 mprecise maps the agent might realize that a road will take slightly longe
 r than expected when arriving on it. To deal with those deviations\, it is
  natural to assume that the agent is able to adapt to the situation: When 
 realizing that taking a particular road is more expensive than expected\, 
 recalculating the tour and taking another road instead is possible.\n\nIn 
 a sense\, this setting lies in between the offline travelling salesman pro
 blem\, and the online problem of graph exploration\, as it allows some com
 putation at the beginning\, but remains an online problem during traversal
  through the graph.\n\nWe analyze the competitive ratio of this problem ba
 sed on the pertur- bation factor α of the edge weights. For general graphs
  we show that for realistic factors smaller than 2 there is no strategy th
 at achieves a competitive ratio better than α\, which can be matched by a 
 simple algorithm.\n\nIn addition\, we prove an algorithm which has a compe
 titive ratio of (1+α)/2 for restricted graph classes like complete graphs 
 with uniform announced edge weights. Here\, we present a matching lower bo
 und as well\, proving that the strategy for those graph classes is best po
 ssible. We conclude with a remark about special graph classes like cycles.
 \n\n\n\n\n\nhttps://algodist.labri.fr/index.php/Main/GT\n\nImport automati
 que depuis https://webmel.u-bordeaux.fr/home/bf-labri.ca@u-bordeaux.fr/gt.
 algo-dist.ics par sync_icals_to_drupal.py pour gt-algodist
DTSTART;TZID=Europe/Paris:20260622T110000
DTEND;TZID=Europe/Paris:20260622T120000
LOCATION:LaBRI 178
SEQUENCE:0
SUMMARY:GT AlgoDist\, «Graph Exploration with Edge Weight Estimates»\, Émil
 e Naquin
TRANSP:OPAQUE
END:VEVENT
END:VCALENDAR
