Seminar: Harold Nieuwboer (UvA & Ruhr University Bochum) and Lucy Verberk (TU/e), 2 PhD-talks

Speaker: Harold Nieuwboer (UvA & Ruhr University Bochum) and Lucy Verberk (TU/e) 

Title:

Harold Nieuwboer: Interior-point methods on manifolds

Lucy Verberk: Stabilization of capacitated matching games

Zoom link: 

https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
(Meeting ID: 849 0964 5595, Passcode: 772448)

Abstract of "Interior-point methods on manifolds" (Harold Nieuwboer):
Interior-point methods offer a highly versatile framework for convex
optimization that is effective in theory and practice. A key notion in
their theory is that of a self-concordant barrier. We give a suitable
generalization of self-concordance to Riemannian manifolds and show that
it gives the same structural results and guarantees as in the Euclidean
setting, in particular local quadratic convergence of Newton's method.
We then analyze a short-step path-following method for optimizing
compatible objectives over a convex domain for which one has a
self-concordant barrier, and obtain the standard complexity guarantees
as in the Euclidean setting. We show that on the positive-definite
matrices and other symmetric spaces, the squared distance to a point is
a self-concordant function. Our work is motivated by recent progress on
scaling problems and non-commutative optimization, and we show that
these fit into our framework, yielding algorithms with state-of-the-art
complexity guarantees. Furthermore, we show how to apply our methods to
computing geometric medians on spaces with constant negative curvature.

Joint work with Michael Walter. Based on https://arxiv.org/abs/2303.04771.

Video of the talk of Harold Nieuwboer: 

Slides of the talk of Harold Nieuwboer:

Slides

Abstract of "Stabilization of capacitated matching games" (Lucy Verberk):
An edge-weighted, vertex-capacitated graph G is called stable if the
value of a maximum-weight capacity-matching equals the value of a
maximum-weight fractional capacity-matching. Stable graphs play a key
role in characterizing the existence of stable solutions for popular
combinatorial games that involve the structure of matchings in graphs,
such as network bargaining games and cooperative matching games.

The vertex-stabilizer problem asks to compute a minimum number of
players to block (i.e., vertices of G to remove) in order to ensure
stability for such games. The problem has been shown to be solvable in
polynomial-time, for unit-capacity graphs. This stays true also if we
impose the restriction that the set of players to block must not
intersect with a given specified maximum matching of G.

We investigate these algorithmic problems in the more general setting of
arbitrary capacities. We show that the vertex-stabilizer problem with
the additional restriction of avoiding a given maximum matching remains
polynomial-time solvable. Differently, without this restriction, the
vertex-stabilizer problem becomes NP-hard and even hard to approximate,
in contrast to the unit-capacity case.

Finally, in unit-capacity graphs there is an equivalence between the
stability of a graph, existence of a stable solution for network
bargaining games, and existence of a stable solution for cooperative
matching games. We show that this equivalence does not extend to the
capacitated case.

Joint work with Matthew Gerstbrein and Laura Sanità. Based on
https://arxiv.org/abs/2211.12179.

Video of the talk of Lucy Verberk:

Slides of the talk of Lucy Verberk:  
Slides