BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//labri.fr//NONSGML kigkonsult.se iCalcreator 2.41.92//
CALSCALE:GREGORIAN
METHOD:PUBLISH
UID:486e08d8-15fb-4bfb-bbe7-d870754fc17b
X-WR-CALNAME:[gt.go] - 'Making Online Algorithms Semi-Online' by Matthias G
 ehnen
X-WR-TIMEZONE:Europe/Paris
BEGIN:VTIMEZONE
TZID:Europe/Paris
TZUNTIL:20251026T010000Z
BEGIN:STANDARD
TZNAME:CET
DTSTART:20231029T030000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
RDATE:20241027T030000
END:STANDARD
BEGIN:DAYLIGHT
TZNAME:CEST
DTSTART:20230326T020000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
RDATE:20240331T020000
RDATE:20250330T020000
END:DAYLIGHT
END:VTIMEZONE
BEGIN:VEVENT
UID:486e08d8-15fb-4bfb-bbe7-d870754fc17b
DTSTAMP:20260513T192450Z
CLASS:PUBLIC
DESCRIPTION:/Exposé /Talk/ \n\n\nIn the classical understanding\, an online
  algorithm gets the instance piece by piece and needs to make some action 
 for every piece of the instance without knowing what comes next. While thi
 s is practical for many problems\, for some it is not. Therefore in recent
  years\, many variants of online problems are studied which relax the sett
 ing. In this talk\, we will discuss some variants: \n\nA common way to pre
 sent graphs in an online fashion is by presenting it vertex-wise\, with al
 l the edges that are induced by the already presented vertices. However\, 
 if an algorithm must decide if each presented vertex is part of a solution
  set or not\, it is easy to find examples for basically every problem that
  show that the approximation ratio of the online algorithm is arbitrary ba
 d in comparison to an optimal solution (this is usually called competitive
  ratio). A way to relax this condition is to not enforce the decision when
 ever the vertex is presented\, but instead only when some property is no l
 onger given. For example\, for an online Feedback Vertex Set\, it is sensi
 ble that the graph is presented vertex-wise\, and the online algorithm onl
 y needs to add a vertex to the solution set as soon as there is an uncover
 ed circle. If the circle is covered\, the instance continues. This concept
  can be found with the name 'Late Accept' or 'Delayed Decision'. We will m
 ainly discuss the Feedback Vertex Set as an example\, which has a competit
 ive ratio of something between four and five. It is even possible to delay
  those decisions more by adding a modification called 'Reservations' [1]. 
 \n\nAnother way of relaxing the online setting is by letting the algorithm
  know about the vague future. For a knapsack problem\, this means that the
  algorithm gets the whole instance in advance\, but only with rough estima
 tes about each item size - which for example can vary of the actual sizes 
 by some percentage. While there is no chance for an online knapsack algori
 thm to achieve any competitive ratio without modification\, this estimates
  actually help. Interestingly\, the competitive ratio does not degrade smo
 othly from an 'good' competive ratio when the estimate is good to a high r
 atio when the estimate gets worse - instead\, there are even jumps in the 
 quality of an algorithm when the estimates degrade [2]. \n\n\n[1] Delaying
  Decisions and Reservation Costs\; E. Burjons\, F. Frei\, M. Gehnen\, H. L
 otze\, D. Mock\, P. Rossmanith\; COCOON 2023 \n[2] Online Simple Knapsack 
 with Bounded Predictions\; M. Gehnen\, H. Lotze\, P. Rossmanith\; STACS 20
 24 \n\n\n[Matthias Gehnen ] (RWTH Aachen ) \nhttps://tcs.rwth-aachen.de/~g
 ehnen/ \n\n\nRemarks / Remarques \n\nFind all the information of the worki
 ng group on this [ https://graphesetoptimisation.labri.fr/pmwiki.php/Group
 e/GT?userlang=en | web page ] . \nRetrouvez toutes les informations du GT 
 sur cette [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT | 
 page web ] .
DTSTART;TZID=Europe/Paris:20240322T140000
DTEND;TZID=Europe/Paris:20240322T150000
LOCATION:LaBRI/178
SEQUENCE:0
SUMMARY:[gt.go] - 'Making Online Algorithms Semi-Online' by Matthias Gehnen
TRANSP:OPAQUE
END:VEVENT
END:VCALENDAR
