1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

Your problem is NP-hard. In particular, 3-dimensional matching is a special case of your problem, and 3-dimensional matching is NP-hard -- so your problem is, too.

$\endgroup$
  • $\begingroup$ Oh boy, that's what I thought. Thanks! $\endgroup$ – Strernd Feb 18 '18 at 11:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.