Fractional 3DM

Consider the well known 3DM problem.

• Instance: let X, Y , Z denote 3 sets of n elements and T ⊆ X × Y × Z a set of triples
• Question: Is there a subset S ⊆ T of n disjoint triples, s.t. every element of X, Y and Z is covered exactly once ?

If you are visiting this page, I bet you know that 3DM is NP-Complete. I look for a fractional solution of 3DM, i.e., are there values V_{x y z} ∈ [0, 1] for each (x, y, z) ∈ T such that

• ∀ x ∈ X, ∑_{(x, y, z) ∈ T} V_{x y z} = 1
• ∀ y ∈ Y, ∑_{(x, y, z) ∈ T} V_{x y z} = 1
• ∀ z ∈ Z, ∑_{(x, y, z) ∈ T} V_{x y z} = 1

Of course such V_{x y z} values can be computed by LP and thus <we have a polynomial time algorithm to get these values. My question is: Is there a combinatorial algorithm to compute the fractional matching ?

This document was translated from L^AT_EX by H^EV^EA.