On Tree-Constrained Matchings and Generalizations
On Tree-Constrained Matchings and Generalizations
复制标题
关于树约束匹配和泛化
作者：
S. Canzar;Khaled M. Elbassioni;G. Klau;Julián Mestre
我们考虑以下树约束二分匹配问题：给定一个二分图 G=(V1,V2,E)，边权重为 documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt}egin{document}$w:Emapstomathbb{R}_{+}$end{document}，集合V1上的有根树T1和集合V1上的有根树T2，找到匹配documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb}的最大权重G 中的 usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$mathcal{M}$end{document} ，这样匹配的节点都不是任一树中另一个匹配节点的祖先。例如，这种经典二分匹配问题的推广出现在活细胞视频数据的计算分析中。我们证明问题是 documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$mathcal{APX}$end{document} -hard，因此，除非documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$mathcal{P} = mathcal{NP}$end{document}，反驳之前的说法，即它可以在多项式时间。此外，我们给出了一种基于局部比率技术和仔细使用自然 LP 松弛基本可行解结构的 2 近似算法，我们还证明了该算法具有 2−o(1) 的完整性差距。在本文的第二部分，我们考虑问题的自然概括，其中树被部分有序集（偏序集）取代。我们证明，局部比率技术为问题的 k 维匹配泛化提供了 2kρ 近似，其中每个偏序集中低于（或高于）任何给定元素的不可比较元素的最大数量以 ρ 为界。我们最后给出了一个几乎匹配的完整性差距示例，以及一个不可近似性结果，表明对 ρ 的依赖很可能是不可避免的。
We consider the following Tree-Constrained Bipartite Matching problem: Given a bipartite graph G=(V1,V2,E) with edge weights documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$w:E mapstomathbb{R}_{+}$end{document}, a rooted tree T1 on the set V1 and a rooted tree T2 on the set V1, find a maximum weight matching documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$mathcal{M}$end{document} in G, such that none of the matched nodes is an ancestor of another matched node in either of the trees. This generalization of the classical bipartite matching problem appears, for example, in the computational analysis of live cell video data. We show that the problem is documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$mathcal{APX}$end{document}-hard and thus, unless documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$mathcal{P} = mathcal{NP}$end{document}, disprove a previous claim that it is solvable in polynomial time. Furthermore, we give a 2-approximation algorithm based on a combination of the local ratio technique and a careful use of the structure of basic feasible solutions of a natural LP-relaxation, which we also show to have an integrality gap of 2−o(1). In the second part of the paper, we consider a natural generalization of the problem, where trees are replaced by partially ordered sets (posets). We show that the local ratio technique gives a 2kρ-approximation for the k-dimensional matching generalization of the problem, in which the maximum number of incomparable elements below (or above) any given element in each poset is bounded by ρ. We finally give an almost matching integrality gap example, and an inapproximability result showing that the dependence on ρ is most likely unavoidable.