# Algorithm for 3-object matching

I believe that in the general case stable matching for 3 members rather than 2 is NP-Complete, but I wonder if in my case there's something that I am missing that could have reasonable time complexity.

The specific purpose of the program I am trying to write is to take an arbitrary number of objects and split them into groups of 3. Hypothetically, each object has a color (let's say right now there's 10 possible colors).

The part of this group creation that allows something of a "preference list" of other members is both having group members of different colors and having been grouped with them in the past as little times as possible.

Everything I have come up with either has horrendous time complexity or has the chance of failing (missing possible groupings). If anyone has done anything like this before I would appreciate any suggestions.

• Welcome to CS.SE! Can you give a more precise statement of the algorithmic task? What are the inputs? What is the desired output? Presumably, you want to find a grouping that satisfies some condition. What is that condition? I don't understand the sentence "The part of this..." -- that is too vague for me. We'll probably need to understand what problem you are trying to solve before we can tell whether it is NP-complete or not.
– D.W.
Jul 30, 2017 at 23:09
• Not clear to me. Are there limits to the size of each group? Aug 1, 2017 at 18:18
• To be more clear, the size of each group should be 3. Ideally the number of objects would be a multiple of three. As for the inputs, there would be a list of objects the program loads, all of which contain a unique identifier, a color, and a list of the other objects it's already been grouped with in past runs. The output should the least conflicted groupings with no repeat objects along with the "conflicts" it contains. A conflict being a grouping with >1 of the same color object or a grouping with objects that have been grouped in the past. Aug 3, 2017 at 14:23
• I believe it makes sense to imagine the output as a list of sports teams (of size 3) for a tournament. While there are technically approximately 10 specializations/positions possible, it would make for the best team if it's members weren't the same specialization/position. Also imagine these players should be socialized, so every time a tournament is made players being on a team with past teammates should be avoided. Aug 3, 2017 at 14:35

In 2014, Ostrovsky and Rosenbaum proved that 3D matching is APX-complete. This implies the existence of an efficient algorithm that produces a result within a "fixed multiplicative factor of the optimal answer" - in their case, $4/9$.