Accueil

Katarzyna Paluch

  1. Popular b-matchings.

    Tue, 01/04/2011 - 16:01 — SomNambul
    Authors: Katarzyna Paluch
    Subjects: Data Structures and Algorithms
    Abstract

    Suppose that each member of a set of agents has a preference list of a subset
    of houses, possibly involving ties and each agent and house has their capacity
    denoting the maximum number of correspondingly agents/houses that can be
    matched to him/her/it. We want to find a matching $M$, for which there is no
    other matching $M'$ such that more agents prefer $M'$ to $M$ than $M$ to $M'$.
    (What it means that an agent prefers one matching to the other is explained in
    the paper.) Popular matchings have been studied quite extensively, especially
    in the one-to-one setting.

  2. Faster and simpler approximation of stable matchings.

    Tue, 12/01/2009 - 16:01 — SomNambul
    Authors: Katarzyna Paluch
    Subjects: Data Structures and Algorithms
    Abstract

    We give a 3/2-approximation algorithm for stable matchings that runs in
    $O(m)$ time. The previously best known algorithm by McDermid has the same
    approximation ratio but runs in $O(n^{3/2}m)$ time, where $n$ denotes the
    number of vertices and $m$ the number of edges. Also the algorithm and the
    analysis are much simpler.

Math-arch

Syndicate content