Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Balanced matchings, unbalanced ones and related problems.
Speaker:Katarzyna Paluch
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:Talk
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Thursday, 21 April 2011
Duration:30 Minutes
Building:E1 4
I will talk about several variations of the matching problem. One of them is as follows.

Suppose we have a graph $G=(V,E)$ and a partition $V_1 \cup V_2 \cup \ldots \cup V_k$ of $V$. We would like to find such a maximum cardinality matching $M$ of $G$
in which roughly the same number of vertices of each $V_i$ are matched. More formally,
we want to find such a maximum cardinality matching $M$, called {\bf balanced matching} that minimises $max\{|s_M(V_i)-s_M(V_j)|: 1 \leq i<j \leq k\}$,
where $s_M(V_i)$ denotes the number of vertices of $V_i$ matched in $M$. I'll show an algorithm that computes a balanced matching via LM-partition matchings.
In the {\bf LM-partition matching problem} we are given besides the graph and the partition of $V$ two parameters for each $i, 1 \leq i \leq k$: $l_i$ and $m_i$ and we wish to find an {\bf LM-partition matching} which is such matching $M$ of $G$, that for each $i$ the number of vertices of $V_i$ matched in $M$ is at least $l_i$ and
at most $m_i$ or ascertain that it does not exist. One can notice that if $l_i=0$ for each $i$ and the given graph $G$ is bipartite ($G=(A \cup B, E))$ and each vertex set of the partition of $V$ is either a subset
of $A$ or a subset of $B$, then an LM-partition matching is the intersection of two matroids. We will not make use of matroids.

Name(s):Katarzyna Paluch
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):

Created:Katarzyna Paluch, 04/18/2011 03:39 PM Last modified:Uwe Brahm/MPII/DE, 11/24/2016 04:13 PM
  • Katarzyna Paluch, 04/20/2011 04:04 PM
  • Katarzyna Paluch, 04/18/2011 03:39 PM -- Created document.