# Best balanced assignment

I'm at a problem I don't know better to name it... maybe it's already a well known problem?

It seems quite simple: There are objects and labels in a n:m relation. (Each of the n objects may be assigned to any subset of the m labels).

Let s be the overall sum of the label-assignments of all objects.

You can take it as a 2-dim binary matrix.

The assigment patterns of the objects define partitions of the objects. (Each partition with equal assignment pattern).

OK, now the input is three numbers: n, m and s.

I am interested in that overall assigment which produces the "most even" partitioning of the objects. (Unassigned objects shall count as a partition of its own).

"Most even": The partition with the most objects shall be as small as possible. (I'm not sure if this is unambiguous and sufficient). The partitions shall be "most evenly distributed".

About alg: Depending on the values I identified several "sub-cases" (from trivial to complex). Very unsatisfying.

Does someone has an idea/ hint how

• to construct a most even partitioning or/ and
• to determine the result ("n1" objects with combination "m1", "n2" objects ...")?

As there was asked for an example:

Let n = 30, m = 5 and s = 50.
Question:
How to distribute the s assigments that the
groups of objects with identical assigment pattern
is most even distributed?

The WORST distribution would be:
X X X X X
X X X X X
(10 lines like that)
O O O O O
O O O O O
(20 lines like that)

==> 2 patterns:
(X X X X X) and (O O O O O)
distributed in the worst way:
20 objects with pattern (O O O O O)
10 objects with pattern (X X X X X)

Another distribution strategy:
O O O O O
O O O O X
O O O X O
O O X O O
O X O O O
X O O O O
Then start from the beginning.
Do that 4 more times (5 times at all)
==> All 30 objects are assigned,
but only 25 assigments set.
==> Add one assigment in every line except the first
Result:
==> 6 patterns, distributed evently
5 objects with pattern O O O O O
5 objects with pattern O O O X X
5 objects with pattern O O X X O
5 objects with pattern O X X O O
5 objects with pattern X X O O O
5 objects with pattern X O O O X
That is pretty well, but obviously it can be done
even better (use pattern with only one X set,
which increases the number of patterns and
by that lowers the number of objects in the groups).

For example "split" the all-unset pattern
3 objects with pattern O O O O O
2 objects with pattern O O O O X
At this point there are 2 assigments too much,
so split the pattern   O O O X X to:
2 objects with pattern O O O X O
3 objects with pattern O O O X X
Result:
3 objects with pattern O O O O O
2 objects with pattern O O O O X
2 objects with pattern O O O X O
3 objects with pattern O O O X X
5 objects with pattern O O X X O
5 objects with pattern O X X O O
5 objects with pattern X X O O O
5 objects with pattern X O O O X
which is wider/ more even distributed.

• I cannot make sense of this. Why do you define a symbol for "objects (o)" ? and then never use "o" in the rest of the description? Same with (p) and (s) . Maybe they should be defined and you should use them in your description to make it more clear - I don't know. Can you elaborate on what you mean by "Now assignments (s) can be done freely into that matrix" ? What is being assigned, and what possible types of assignments can be made? You are talking about quantities being "as small as possible". Where are there any values to use? Do your objects have values in them? This needs re-writing
– JimN
Commented Apr 26, 2023 at 23:32
• Thanks for the feedback. I did a re-writing to (hopefully) make it more clear. Commented Apr 27, 2023 at 8:01
• What is meant by "the overall sum of the label-assignments"? What's the context or motivation for this problem?
– D.W.
Commented Apr 27, 2023 at 18:30
• s = the sum of all assigments (the number of the "1"s in the matrix). Strange. I must have explained it much too complicated... Just think of the very simplest of assigments. Commented Apr 27, 2023 at 22:02
• Perhaps your problem statement could be improved with a small illustrative example.
– JimN
Commented Apr 28, 2023 at 15:02

If $$n\le m$$: Assign each object to all but one label (a different missing label for each object). Then $$s=n(m-1)$$ is the maximum attainable.

Otherwise, if $$n\le {m \choose 2}$$: Assign each object to all but two labels (a different pair of missing labels for each object). Then $$s=n(m-2)$$ is the maximum attainable.

Otherwise, if $$n\le {m \choose 3}$$: Assign each object to all but three labels (a different triple of missing labels for each object). Then $$s=n(m-3)$$ is the maximum attainable.

etc.

You should be able to take it from here and turn it into an algorithm.

• Thankyou for your feedback. Still you get me wrong. I am not searching for a maximum of assigments for given n and m. The number of assigments s is an input of the problem. Meanwhile I rewrote my description and added an example. Still it's nice to see you get upvoted (for a non-fitting answer) while I got honoured by being downvoted (for answering immediately, trying to clear up etc. in one of my first posts). Commented Apr 28, 2023 at 18:18
• @User42, I know. I did understand that. It is easy to start from this solution and reduce the number of assignments. If you work through this, this should have the main ideas needed for you to create an algorithm for your problem.
– D.W.
Commented Apr 28, 2023 at 18:21
• @User42 is your difficulty in accepting this answer because you need more details on how to distribute those labels in each row? (@D.W. says "a different pair/triple of missing labels for each object"). It might be the case that you want that specific detail filled in (?)
– JimN
Commented Apr 28, 2023 at 18:32
• I'm sorry but I don't understand any connection between my problem and your alg... For example (first branch), let n=10, m=13, you build all patterns each with one label unset. That means 10 * 12 assigments. And now? How do I get from here to the input s (0 <= s <= 10 * 13)? What if s > 120? Moreover: The example from my first post (n=30, m=5): there is no branch for that in your alg... I've the impression we're terribly misunderstanding Commented Apr 28, 2023 at 22:08
• @User42, 1. If $n=10,m=13$ and $s=120$, then my answer gives you a solution. 2. If $n=10,m=13$ and $s<120$, then it is easy to adapt my answer to a solution: it is easy to start with my answer and then reduce the number of assignments. 3. If $n=10,m=13$ and $s>120$, then there is no solution. As I wrote, $s=n(m-1)$ is the maximum attainable. You're going to have to take it from here. I have given you the main idea. This is your exercise, and so you'll need to fill in the remaining details.
– D.W.
Commented Apr 28, 2023 at 22:18