Description
EGERVÁRY SZEMINÁRIUM
Absztrakt: We give simple approximation algorithms for common
generalizations of many previously studied extensions of the stable
and popular matching problems with ties. These generalizations include
the existence of critical agents, amongst whom we must match as much
as possible, free edges, that cannot be blocking edges and
Δ-stabilities, which mean that for an edge to block, the improvement
should be large enough on one or both sides and many more. We
introduce a new, natural notion of popularity in the presence of ties,
which we call weak popularity. We give a 3/2-approximation algorithm
for finding a maximum size stable matching in our general model and a
4/3-approximation algorithm for finding a maximum size weakly popular
matching. We also show that these ratios are best possible under known
complexity theoretic assumptions.