2
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – D.W. ♦
    Jul 30, 2017 at 23:09
  • $\begingroup$ Not clear to me. Are there limits to the size of each group? $\endgroup$
    – paparazzo
    Aug 1, 2017 at 18:18
  • $\begingroup$ 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. $\endgroup$
    – user75532
    Aug 3, 2017 at 14:23
  • $\begingroup$ 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. $\endgroup$
    – user75532
    Aug 3, 2017 at 14:35

1 Answer 1

Reset to default
1
$\begingroup$

It sounds like you're looking for a polynomial-time approximation algorithm for the 3-dimensional matching problem (which is, as you noted, NP-complete - the decision problem is one of Karp's 21 NP-complete problems).

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$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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