28 września 2021 10:15
[Seminarium ZOK] Jarosław Byrka: "Submodularity Gaps for Selected Network Design and Matching Problems"
Streszczenie:
Several techniques that allow developing approximation
algorithms for problems with submodular cost function have been proposed. One can therefore ask whether it is
possible to approximate the actual cost function of a studied problem with a proxy submodular
function. Existence of such submodular approximations would allow to reduce various problems to
submodular optimisation.
We answer this question in the negative for two major problems in metric optimization, namely
Steiner Tree and Uncapacitated Facility Location. We do so by proving super-constant lower bounds
on the submodularity gap for these problems. Our bounds build on strong lower bounds for the
online variants of these two problems. Additionally, we show that the problem Maximum Bipartite
Matching does not exhibit a submodularity gap, in contrast with its online variant being only
(1−1/e)-competitive in the randomized setting.
This is a joint work with Martin Böhm, Mateusz Lewandowski and Jan Marcinkowski.