Fast approximation algorithms for weighted matching in graphs
and hypergraphs

                       Robert Preis
Sandia National Laboratories, Albuquerque, NM USA
                           and
             University of Paderborn, Germany

A data set with dependencies among  the data elements can
be viewed as a dependency graph or hypergraph and is
common in many scientific applications. Typical tasks on
the data set include  the efficient parallel execution of
code associated with the data elements, visualization of the
data elements,  or partitioning or clustering of
the data elements into subsets taking into consideration
the   constraints imposed by the dependencies.
Graph matching and hypergraph matching  algorithms often play an
essential role in the kernels of these tasks.

A matching in a graph G=(V,E) is a  subset of
the edge set E such that two edges do not share a common endpoint.
The weight of a  matching is the sum of the
weights of the edges in the matching.
Although a maximum weighted matching can be
computed in polynomial time of O(|E|*|V|), faster
algorithms are attractive  in many settings if they are able
to guarantee that there is only a small gap between their
solution quality and that of an optimal algorithm.

We present approximation algorithms for the maximum
weighted matching problem that run in linear time O(|E|)
and guarantee a solution quality within a factor of two
from the optimal. We  generalize these algorithms to
the weighted hypergraph matching problem
(also known as the weighted k-set packing problem);
here the approximation guarantee is  a factor at most k,
where k is the maximum number of vertices in a hyperedge,
and the approximation algorithm still runs in linear time.


--