1
$\begingroup$

I'm trying to solve an optimization problem which can be described as follows.

  • There are four sets objects. For simplicity, let's call them :
    1. Apples
    2. Oranges
    3. Pears
    4. Lemons
  • The sets can contain unequal numbers of their respective objects
  • These objects must be organized into groups containing exactly one of each object
  • Each possible group can be evaluated by some merit function (ie: function of the difference between the masses of the constituent objects of the group, say)
  • The maximum number of groups with a merit function below some threshold must be formed with the objects in the input sets.
  • In the above set of groups, no object can be duplicated - it must belong uniquely to one group.

My question is not necessarily how to solve this problem - this is no doubt an extremely broad question. What I would like to know is whether or not this problem has, or is of a class of problem, with some formal name.

Primarily, I'm looking for search terms to help research similar problems (and the types of solutions that are known for it).

Improve this question
$\endgroup$
4
  • $\begingroup$ Seems like a complicated version of the knapsack problem. $\endgroup$
    – André Souza Lemos
    Commented May 11, 2015 at 21:07
  • $\begingroup$ @AndréSouzaLemos That actually got me started down the right road, I think. This is perhaps closer to the Stable Marriage problem, albeit with a marriage of four genders rather than two. en.wikipedia.org/wiki/Stable_marriage_problem#Similar_problems $\endgroup$
    – J...
    Commented May 11, 2015 at 21:25
  • 1
    $\begingroup$ The thing is, you are selecting a subset of the total number of possible matches, according to an decision function. That's what brings it closer to knapsack. Appearances deceive. $\endgroup$
    – André Souza Lemos
    Commented May 11, 2015 at 21:29
  • $\begingroup$ @AndréSouzaLemos Yes, but with many knapsacks...the number of which is also a parameter to be optimized. I'll keep reading, this is a good start, thanks! $\endgroup$
    – J...
    Commented May 11, 2015 at 21:41

1 Answer 1

Reset to default
3
$\begingroup$

It's called four-dimensional matching and it's NP-complete.

Improve this answer
$\endgroup$
10
  • $\begingroup$ I was pretty certain from the formulation that it must be NP-complete. At best I'm hoping to find some workable approximations. I'll look this up! $\endgroup$
    – J...
    Commented May 11, 2015 at 22:12
  • $\begingroup$ You might find more information on three-dimensional matching, which might still be helpful. $\endgroup$
    – David Richerby
    Commented May 11, 2015 at 22:17
  • $\begingroup$ Indeed, reading up on it now... $\endgroup$
    – J...
    Commented May 11, 2015 at 22:17
  • $\begingroup$ It seems that n-Dim matching assumes T (set of n-ples) is given as input. In my case this is not so - all I have are the initial disjoint sets. I suppose the problem would reduce to first a knapsack-type problem for the generation of the initial set of T, followed by a weighted form of maximum n-Dim matching to reduce T. $\endgroup$
    – J...
    Commented May 12, 2015 at 9:10
  • $\begingroup$ In your case, $T$ is just the set $\mathrm{Apples}\times\mathrm{Oranges}\times\mathrm{Pears}\times\mathrm{Lemons}$. Worst case, you could generate this list; I don't know what algorithms for 4DM look like but it's possible that you could do something smarter than that and use the "implicit" representation for the set of tuples and their weights throughout your algorithm. $\endgroup$
    – David Richerby
    Commented May 12, 2015 at 9:25

Your Answer

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

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