TY - GEN

T1 - On tree-constrained matchings and generalizations

AU - Canzar, Stefan

AU - Elbassioni, Khaled

AU - Klau, Gunnar W.

AU - Mestre, Julián

PY - 2011

Y1 - 2011

N2 - We consider the following Tree-Constrained Bipartite Matching problem: Given two rooted trees T 1 = (V 1,E 1), T 2 = (V 2,E 2) and a weight function w: V 1x V 2 → ℝ+, find a maximum weight matching between nodes of the two trees, 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 -hard and thus, unless , 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.

AB - We consider the following Tree-Constrained Bipartite Matching problem: Given two rooted trees T 1 = (V 1,E 1), T 2 = (V 2,E 2) and a weight function w: V 1x V 2 → ℝ+, find a maximum weight matching between nodes of the two trees, 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 -hard and thus, unless , 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.

UR - http://www.scopus.com/inward/record.url?scp=79960000698&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=79960000698&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-22006-7_9

DO - 10.1007/978-3-642-22006-7_9

M3 - Conference contribution

AN - SCOPUS:79960000698

SN - 9783642220050

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 98

EP - 109

BT - Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Proceedings

T2 - 38th International Colloquium on Automata, Languages and Programming, ICALP 2011

Y2 - 4 July 2011 through 8 July 2011

ER -