Anzeige
Erschienen in:
2006 | OriginalPaper | Buchkapitel
On Load-Balanced Semi-matchings for Weighted Bipartite Graphs
verfasst von : Chor Ping Low
Erschienen in: Theory and Applications of Models of Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
A
semi-matching
on a bipartite graph
G
=(
U
∪
V
,
E
) is a set of edges
X
⊆
E
such that each vertex in
U
is incident to exactly one edge in
X
. The sum of the weights of the vertices from
U
that are assigned (semi-matched) to some vertex
v
∈
V
is referred to as the
load
of vertex
v
. In this paper, we consider the problem to finding a semi-matching that minimizes the maximum load among all vertices in
V
. This problem has been shown to be solvable in polynomial time by Harvey et. al [3] and Fakcharoenphol et. al [5] for unweighted graphs. However, the computational complexity for the weighted version of the problem was left as an open problem. In this paper, we prove that the problem of finding a semi-matching that minimizes the maximum load among all vertices in a weighted bipartite graph is NP-complete. A
$\frac{3}{2}$
-approximation algorithm is proposed for this problem.