Engineering of Approximation Algorithms for Matching and Covering in Hypergraphs and Large Graphs

This page describes our project in the DFG Priority Program Algorithm Engineering. The priority program also has a central website.

Overview

Matching in Hypergraphs

In the b-matching problem, we aim to select as many edges from a hypergraph as possible while allowing only b of them to overlap in each vertex. This problem and related ones have many applications in medicine, computational geometry, and combinatorial auctions. The b-matching problem is NP-hard even if restricting to simple-structured instances. For large b, constant-factor approximations are achieved by randomized rounding. However, applications often demand small b. For small b, oblivious greedy algorithms are state-of-the-art on the theoretical side; those incorporate graph parameters such as the number of vertices in the approximation guarantee.

A goal of our project is the development of non-oblivious algorithms that work well for small b, and better than the oblivious ones. We consider combinatorial and LP-based techniques, separately as well as in combination. At the same time, we improve the known inapproximability theory.

Matching in Large Graphs

With graphs containing a large number of edges, the random access model has to be reconsidered, since random access can result in excessive seek times. The new approach is to treat a graph as a stream of edges. Algorithms now cannot simply determine, e.g., whether two vertices are adjacent or not. Instead, algorithms have to make use of edges as they go by in the stream. They may pass over the stream multiple times, but the number of passes should be strictly limited.

In our project we design streaming algorithms for matching in bipartite and general graphs. In the first phase, we presented an approximation scheme for the bipartite case and proved a worst-case bound on the number of passes depending only polynomially on the approximation parameter. Ongoing research is concerned with experimentally analyzing and improving this algorithm. Moreover, the extension to general graphs is investigated.

Involved Scientists

Events

Publications

For a list of publications, please consult our project page at the central website.