On Linear and Semidefinite Programming Relaxations for Hypergraph Matching

被引：0
作者：
Chan, Yuk Hei [1 ]
Lau, Lap Chi [1 ]
机构：
[1] Chinese Univ Hong Kong, Dept Comp Sci & Engn, Hong Kong, Hong Kong, Peoples R China
来源：
PROCEEDINGS OF THE TWENTY-FIRST ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS | 2010年 / 135卷
关键词：
APPROXIMATION ALGORITHM; LOVASZ-SCHRIJVER; SET; THEOREM; NUMBER;
D O I：
暂无
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
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 tins problem ate all local search algorithms hi this paper we analyze different, lineal and semidefinite programming relaxations for the hypergraph matching problem, and study their connections to the local search method Our Main results are the following
引用
收藏
页码：1500 / 1511
页数：12
相关论文
共 53 条
[1]  
Aharoni R, 2000, J GRAPH THEOR, V35, P83, DOI 10.1002/1097-0118(200010)35:2<83::AID-JGT2>3.0.CO
[2]  
2-V
[3]   Ryser's conjecture for tripartite 3-graphs [J].
Aharoni, R .
COMBINATORICA, 2001, 21 (01) :1-4
[4]   Approximating the independence number via the θ-function [J].
Alon, N ;
Kahale, N .
MATHEMATICAL PROGRAMMING, 1998, 80 (03) :253-264
[5]  
[Anonymous], 2006, P 38 ANN ACM S SEOR
[6]  
[Anonymous], 1973, INFINITE FINITE SETS
[7]  
[Anonymous], 2001, P 33 ANN ACM S THEOR
[8]   On local search for weighted k-set packing [J].
Arkin, EM ;
Hassin, R .
MATHEMATICS OF OPERATIONS RESEARCH, 1998, 23 (03) :640-648
[9]  
Arora S, 2002, ANN IEEE SYMP FOUND, P313, DOI 10.1109/SFCS.2002.1181954
[10]  
ASADPOUR A, 2008, P 11 INT WORKSH APPR, P10
123456