Campus Event Calendar

Event Entry

New for: D3

What and Who

On Linear Programming Relaxations of Hypergraph Matching

Yuk Hei Chan
The Chinese University of Hong Kong
PhD Application Talk
AG 1, AG 3, AG 4, AG 5, SWS, RG1, MMCI  
Public Audience

Date, Time and Location

Tuesday, 16 February 2010
120 Minutes
E1 4


A hypergraph is a generalization of a graph where each hyperedge can contain an arbitrary number of vertices. The hypergraph matching problem is to find a largest collection of disjoint hyperedges. While matching on general graphs is polynomial time solvable, hypergraph matching is NP-hard and there

is no good approximation algorithm for the problem in its most general form. We study the restricted case where every hyperedge consists of k vertices, known as k-Set Packing.

We show that the integrality gap (the maximum ratio of the fractional solution to the integral solution over all hypergraphs) is k-1+1/k, and that the integrality gap analysis is tight in general. The proof is by showing a fractional colouring with a small number of colours. The colouring is done in a greedy manner with the help of a good ordering of hyperedges, which is derived from the LP solution.

As a special case, we prove that by adding a Fano plane constraint which deals with a set of intersecting hyperedges, the integrality gap of the LP for unweighted 3-Set Packing can be improved from 7/3 to 2. The result is by detailed analysis on the structure of a counterexample H, where we show that there is no Fano plane in H and by a result of Furedi [F81], we conclude that the integrality gap is 2.

When the vertex set is partitioned into k sets so that each hyperedge contains one vertex from each set, we have the k-Dimensional Matching problem. In this case we show that the standard LP relaxation has an integrality gap of k-1. We remark that integrality gap analysis had been made by Furedi, Kahn and
Seymour [FKS93] in a more general form using a different approach, but their analysis does not directly yield an approximation algorithm. We obtain a (k-1)-approximation algorithm by combining the good ordering on thehyperedges with an algorithmic framework called local-ratio. This improves the previous
result for 3-Dimensional Matching from 2+\epsilon to 2.


IMPRS-CS Office Team
0681 93 25 225
--email hidden
passcode not visible
logged in users only

Stephanie Jörg, 02/12/2010 10:17 -- Created document.