Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am searching for a consolidated model to group n items in x groups. Do you know how to find on the web some resources on the above subject?

In my idea it can be something like: I have 4 persons and 2 groups of 2 persons each. The "friendship" level can be set on a range from 10 to -10

   A  B  C  D
A  X  9  0 -1
B  9  X  5 -5 
C  0  5  X  0
D -1 -5  0  X

would group A&B (friendship level 9) and C&D (friendship level 0) because it maximize the overall friendship level respecting the constraint over groups (9 + 0 = 9 best possible choice).

To sum up

Input Data:

  • n items with measures associated (with must and mustn't group with...)

  • x groups (each with its own size i.e. group1 -> 5 items, group2 --> 15 and so on)

Output data:

  • Best or sub optimal choice(s)

So a most complex example can be:

I have 16 persons to divide as:

  • Group 1: 2 persons
  • Group 2: 2 persons
  • Group 3: 4 persons
  • Group 4: 8 persons

You have the same friendship level, but in my idea I would add or a side-logic for forcing grouping and ungrouping or use a fake level (say 10k or -10k) to enforce the same behaviour.

EDIT @Joriki: for groups of more than 2 persons logic does not change, meaning that if AB=5, BC=2, AC = -1, friendship level is 6 (=5+2+(-1))

EDIT2: In my example I was using sums, but every suggestion is welcome. Joriki pointed out the use of products. I think it is a good idea indeed but then negative values won't be used any longer.

Any hint on a model / algorithm that can be adapted to the above case?

Thx

share|improve this question
    
you have an example of what it can't be, but do you have an example of what it can be? I don't understand what you're trying to do. –  Patrick Da Silva Jul 18 '11 at 8:45
    
Sorry, it was a typo. I edit it now! –  Mauro Jul 18 '11 at 8:51
    
I removed the model-theory tag, as it is intended to refer to this. –  t.b. Jul 18 '11 at 9:47
    
I don't understand your example. It might clarify the question if you explain why A & B and C & D would be grouped together. Also the description under "Input Data" could use some clarification/explication. –  joriki Jul 18 '11 at 9:55
    
Yeah, it's still unclear. Can you give more examples or give us an idea of what does those measures mean and how does the group gets chosen? I know that's almost actually your question, but we don't understand what you want to find (at least me and joriki!) –  Patrick Da Silva Jul 18 '11 at 9:59

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.