A Framework for Approximating Solutions Rather than Solution Values Parameterized by TreewidthOberseminar Discrete Optimization
by
Arithmeum, Lennéstr., 2 - Seminarraum
Arithmeum / Research Institute for Discrete Mathematics
We often find ourselves asking for optimal solutions for a computational problem but having good reasons to believe such solutions cannot be found efficiently. Examples of this include a selecting value-maximizing items to carry in a Knapsack with a given capacity, or assigning consumers to facilities in a network so that each consumer's demand is met by what the facilities can supply. One well-established way of approaching such situations is to ask for approximately optimal solutions rather than optimal solutions which sometimes can make efficient computation possible. This allows to give almost optimal solutions. However, there is also a second natural and much less explored approach we can take, namely to relax the constraints a solution needs to meet. In the above examples this could mean allowing to exceed the size of a Knapsack or the capacities of facilities slightly. In this talk, we formally define this alternative notion of approximation and describe a general meta-theorem to obtain corresponding approximation algorithms on tree-like graphs based on the proof of a new generalization of Courcelle’s theorem.
This talk is based on joint work with Jan Dreier and Robert Ganian appearing at LICS 2025.
The Oberseminar takes place in the Seminarraum, 1st floor. Participants are invited to have coffee or tea in the lounge before.
S. Held, S. Hougardy, L. Végh, J. Vygen