Let P be a set of 3k points in the Euclidean plane. A 3-matching is a partition of P into k subsets of 3 points each, called triplets. The cost of each triplet fa; b; cg is given by minfjabj + jbcj; jbcj + jcaj; jcaj + ...