An approximation algorithm for the load-balanced semi-matching problem in weighted bipartite graphs

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, w...

Full description

Saved in:
Bibliographic Details
Published in:Information processing letters 2006-11, Vol.100 (4), p.154-161
Main Author: Low, Chor Ping
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Algorithms
Applied sciences
Approximation
Approximation algorithms
Bipartite graphs
Codes
Combinatorics
Combinatorics. Ordered structures
Computer science
control theory
systems
Exact sciences and technology
Graph algorithms
Graph theory
Graphs
Load balancing
Mathematics
NP-hard
Sciences and techniques of general use
Semi-matching
Studies
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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. [N. Harvey, R. Ladner, L. Lovasz, T. Tamir, Semi-matchings for bipartite graphs and load balancing, in: Proc. 8th WADS, 2003, pp. 284–306] and Fakcharoenphol et al. [J. Fakcharoenphol, B. Lekhanukit, D. Nanongkai, A faster algorithm for optimal semi-matching, Manuscript, 2005] 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 3 2 -approximation algorithm is proposed for this problem.
ISSN:0020-0190
1872-6119
DOI:10.1016/j.ipl.2006.06.004