On linear and semidefinite programming relaxations for hypergraph matching

• 成果类型: Article
• 署名作者: Chan, Yuk Hei; Lau, Lap Chi
• 署名单位: Chinese University of Hong Kong
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-011-0451-5
• 发表日期: 2012
• 页码: 123-148
• 关键词: sherali-adams; approximation algorithm; integrality gaps; lovasz-schrijver; set; THEOREM; number

摘要

The hypergraph matching problem is to find a largest collection of disjoint hyperedges in a hypergraph. This is a well-studied problem in combinatorial optimization and graph theory with various applications. The best known approximation algorithms for this problem are all local search algorithms. In this paper we analyze different linear and semidefinite programming relaxations for the hypergraph matching problem, and study their connections to the local search method. Our main results are the following: We consider the standard linear programming relaxation of the problem. We provide an algorithmic proof of a result of Furedi, Kahn and Seymour, showing that the integrality gap is exactly for k-uniform hypergraphs, and is exactly k - 1 for k-partite hypergraphs. This yields an improved approximation algorithm for the weighted 3-dimensional matching problem. Our algorithm combines the use of the iterative rounding method and the fractional local ratio method, showing a new way to round linear programming solutions for packing problems. We study the strengthening of the standard LP relaxation by local constraints. We show that, even after linear number of rounds of the Sherali-Adams lift-and-project procedure on the standard LP relaxation, there are k-uniform hypergraphs with integrality gap at least k - 2. On the other hand, we prove that for every constant k, there is a strengthening of the standard LP relaxation by only a polynomial number of constraints, with integrality gap at most for k-uniform hypergraphs. The construction uses a result in extremal combinatorics. We consider the standard semidefinite programming relaxation of the problem. We prove that the Lovasz -function provides an SDP relaxation with integrality gap at most . The proof gives an indirect way (not by a rounding algorithm) to bound the ratio between any local optimal solution and any optimal SDP solution. This shows a new connection between local search and linear and semidefinite programming relaxations.