2
$\begingroup$
  • Premise:
    • There are several balls, and each ball has a color.
    • Each ball is also labeled with either 0 or 1.
    • These balls are randomly placed in boxes as follows:
Box A: red-0, blue-1, yellow-0
Box B: blue-0, yellow-0
Box C: red-1, blue-0, yellow-1
etc...

  • Problem:

    • Create an algorithm to maximize the number of boxes that contain only balls labeled with 1 by exchanging balls multiple times under the following conditions.

  • Conditions:

    • Balls can only be exchanged with other balls of the same color.
    • The procedure should be carried out with the minimum number of steps.

And my question is

  • Is it possible to formulate this problem?
  • What algorithms would work?

Thank you so much in advance for your interest.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

This problem is NP-hard, by a reduction from set packing. For element we create a color, and for every set we create a box (with the colors of its elements). For every color all of its instances are labelled 0, except one arbitrary one which is labelled with 1.

Now the maximum number of boxes which contain only balls labelled with 1 is the size of the maximum set packing.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thank you for your clear answer. Do you have any ideas on what algorithms would work? $\endgroup$
    – Tetsuro Nakamura
    Commented Jul 27 at 13:16
  • $\begingroup$ When you have a small number of colors you can consider the vector of how many times each of the colors in the sets you choose to be filled appears, and then do DP on that $\endgroup$
    – Daniel Weber
    Commented Jul 27 at 15:29
  • $\begingroup$ > except one arbitrary one which is labelled with 1. The problem here does not limit the case to where there are only one ball labelled with 1 among the color. Even under that assumption, can it be said that it is the same as the set packing problem? $\endgroup$
    – Tetsuro Nakamura
    Commented Jul 30 at 7:47
  • $\begingroup$ I don't understand your question $\endgroup$
    – Daniel Weber
    Commented Jul 30 at 11:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .