# Find the best set of triples of objects, using each object at max one time

I stumbled upon an interesting problem and I'm stuck with it, since I can't find parallels to other problems or algorithms to solve it.

We have a set of objects $O = \{a,b,c,...,z\}$, objects can make triples, e.g. $T=(a,b,c)$ $a,b,c \in O$ and we have a set of triples $X = \{T_1, ... T_n\}$. Each triple is assigned a value $c: X \rightarrow \mathbb{R}$

• not every object has to be in a triple
• an object can be in multiple triples
• there can be triples using the same objects, but in a different order e.g. $(a,b,c),(c,a,b)$

Goal: Find the subset of triples $S \subseteq X$, where $\forall x \in \bigcup S: \exists y \in \bigcup S => y =x$ (Every object may appear at most once in the selection) with maximum $\sum_{T \in S} c(T)$ (maximum value of selection).

Is there a fast way to get the maximum? If not, is there any fast strategy that may produce a good result?

A simple greedy strategy would be to sort the triples descending by value and take a triple into the subset if all of it's objects are unused. This can be done in $O(n \log n)$, but does not produce the optimal result.