2
$\begingroup$

Note: I know the numbers are arbitrary, but this problem about this size has practical implications. It is an applied algorithm problem.

Suppose you have 200 bins. Each bin would be very happy to have the integer sequence: 1, 2, 3, 4, 5, 6, 7, 8, 9. And the algorithm would be very happy if all bins get that.

The algorithm is allowed to choose four 3-tuples from a collection of 800 3-tuples. It will assign assign 4 of them to each bin. So each bin will have four 3-tuples assigned to them. These 3-tuples have the following properties:

  1. They are pseudo-randomly generated all at once as a collection of 800 3-tuples.
  2. Each number in a generated 3-tuple is unique. For example, (1, 1, 2) and (7, 4, 4) are impossible but (1, 2, 3) and (8, 2, 9) are possible.
  3. Each value within the 3-tuple can only be a number from 1 to 9. For example, (10, 3, 15) is an impossible tuple. The 3 could occur, but 10 and 15 could not.

A corollary from point 1 is that it could be the case that some integers occur less than the amount of bins that exist. In such a case the application would be very happy if as many bins get a numerical sequence from 1 to 9 and the other bins get as close as possible to such a sequence. For example, suppose that the number 9 has been randomly generated in 180 3-tuples, then at least 20 bins will not get the number 9, but they hopefully should be able to get the integers 1 to 8.

Here is an example of 2 bins and 8 3-tuples. The following numbers are pseudo-randomly generated.

(3, 8, 2) 
(2, 1, 5) 
(2, 7, 8) 
(7, 8, 5)
(7, 8, 4)
(7, 5, 8)
(7, 9, 5)
(4, 7, 3)

Assigning them to two bins as optimal as possible by the requirements yields:

Bin 1 - Sequence: 1, 2, 3, 4, 5, 7, 8, 9
(2, 1, 5)
(4, 7, 3)
(7, 9, 5)
(7, 8, 5)

Bin 2 - Sequence: 2, 3, 4, 5, 7, 8
(2, 7, 8) 
(7, 8, 4)
(7, 5, 8)
(3, 8, 2)

Note: in this particular example there is no 6. There is one 1 and one 9. This means that the 1 and the 9 automatically go to Bin 1. The integer 6, well it simply isn't there, so it cannot be assigned to a bin.

My first question: Design an algorithm that ensures the most optimal solution.

My second question: is a generalized or analogous version known as a certain problem or field in mathematics?

I suppose this problem is a variant of the set cover problem. However, instead of covering a universe, 200 'universes' need to be covered. Or said in another way: the universe needs to be covered 200 times in such a way that the cover can be split up into 200 groups of four 3-tuples.

$\endgroup$
1
$\begingroup$

I suspect finding the optimal assignment will be NP-hard in theory and possibly hard in practice, but it might be possible to find a near-optimal solution.

One approach is to express this as an instance of integer linear programming, and use an off-the-shelf ILP solver. Let $x_{i,j}$ be a zero-or-one integer variable, with the intended meaning that $x_{i,j}=1$ implies the $i$th tuple is assigned to the $j$th bin, and $y_{j,d}$ another zero-or-one variable, with the intended meaning that $y_{j,d}=1$ means that digit $d$ is covered in bin $j$. Then you can write down a set of linear inequalities on the $x$'s and $y$'s that captures what constitutes a consistent and valid solution.

For instance, the constraints might be: $\sum_j x_{i,j} = 1$ (each tuple is assigned to one bin), $\sum_i x_{i,j}=4$ (each bin receives 4 tuples), $y_{j,d} \ge x_{i,j}$ if the $i$th tuple contains digit $d$, and $y_{j,d} \le \sum_i x_{i,j}$ where the sum is over all tuples $i$ that contain digit $d$. Now you want to maximize the linear objective function $\sum_{j,d} y_{j,d}$. Then, you could use an off-the-shelf ILP solver to try to find an optimal solution to this linear program, or ask it to report the best solution it can find within a given time bound.

I don't know if there is a better approach. You could look at algorithms for exact cover to see if any of them can be adapted to your setting.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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