BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//CERN//INDICO//EN
BEGIN:VEVENT
SUMMARY:A Framework for Approximating Solutions Rather than Solution Value
 s Parameterized by Treewidth [Oberseminar Discrete Optimization]
DTSTART:20250630T161500Z
DTEND:20250630T171500Z
DTSTAMP:20260317T061900Z
UID:indico-event-341@math-events.uni-bonn.de
DESCRIPTION:Speakers: Thekla Hamm (Eindhoven University of Technology)\n\n
 We often find ourselves asking for optimal solutions for a computational p
 roblem but having good reasons to believe such solutions cannot be found e
 fficiently. Examples of this include a selecting value-maximizing items to
  carry in a Knapsack with a given capacity\, or assigning consumers to fac
 ilities in a network so that each consumer's demand is met by what the fac
 ilities can supply. One well-established way of approaching such situation
 s is to ask for approximately optimal solutions rather than optimal soluti
 ons which sometimes can make efficient computation possible. This allows t
 o give almost optimal solutions. However\, there is also a second natural 
 and much less explored approach we can take\, namely to relax the constrai
 nts a solution needs to meet. In the above examples this could mean allowi
 ng to exceed the size of a Knapsack or the capacities of facilities slight
 ly. In this talk\, we formally define this alternative notion of approxima
 tion and describe a general meta-theorem to obtain corresponding approxima
 tion algorithms on tree-like graphs based on the proof of a new generaliza
 tion of Courcelle’s theorem.\n \nThis talk is based on joint work with 
 Jan Dreier and Robert Ganian appearing at LICS 2025.\n \nThe Oberseminar 
 takes place in the Seminarraum\, 1st floor. Participants are invited to ha
 ve coffee or tea in the lounge before.\n\nhttps://math-events.uni-bonn.de/
 event/341/
LOCATION:Arithmeum\, Lennéstr.\,  2 - Seminarraum (Arithmeum / Research I
 nstitute for Discrete Mathematics)
URL:https://math-events.uni-bonn.de/event/341/
END:VEVENT
END:VCALENDAR