Solving the Multiset Filling Problem

  • Thread starter mXSCNT
  • Start date
In summary, the conversation discusses a problem related to a thread on Physics Forums, where a set A contains multisets of positive real numbers that add up to 1. The goal is to find a multiset B that can be surjected onto each element in A, while minimizing the size of B. This problem can also be applied to countably infinite sets. A possible solution is given for the finite case, but it may not always minimize the size of B. The conversation also mentions a special case where a solution for B can be found with a size equal to the least common multiple of the elements in A. Finally, it is stated that it is not possible to find a solution where the size of B is less than the least common
  • #1
mXSCNT
315
1
This is closely related to the problem posed in https://www.physicsforums.com/showthread.php?t=287947, but stated in simpler, non-probabilistic terms.

Suppose we have a set, [tex]A = \{a_j : j \in 1,2,..,n\}[/tex]. Each aj is a multiset (meaning repetitions are allowed) of positive real numbers, where [tex]\sum_{y \in a_j} y = 1[/tex]. We want to find a multiset B of positive real numbers, such that for each j, there is a surjective function [tex]f_j : B \rightarrow a_j[/tex] such that

[tex]\forall y \in a_j, y = \sum_{x \in f_j^{-1}(y)} x[/tex].

Additionally we would like to minimize |B|.

Also of interest is the generalization of the problem to the case when the aj and B might be countably infinite.

Intuitively,one might think of each aj as a bureau with drawers of varying size, and we seek a collection of varying-size bricks B that will fill any bureau exactly.

One possible solution for the finite case (which does not necessarily minimize |B|) is to let
[tex]B = \{\prod_{j=1}^n s_{ij} : \forall j, s_{ij} \in a_j\}[/tex].
What I mean by that notation is, for each sequence si, there is an element of B; since B is a multiset the same product may appear more than once.

Then, for each [tex]x_i = \prod_j s_{ij} \in B[/tex], we can let let [tex]f_j(x_i) = s_{ij}[/tex]. Thus, since [tex]y \in a_j[/tex] is some [tex]s_{ij}[/tex],

[tex]\sum_{x_i \in f_j^{-1}(s_{ij})} x_i = s_{ij} \sum_i (\prod_{k \neq j} s_{ik}) = s_{ij} = y[/tex].

As an example, let A = {{0.6,0.4},{0.5,0.5}}. Then with the above solution, B = {0.3, 0.3, 0.2, 0.2}, and 0.6 = 0.3 + 0.3, 0.4 = 0.2 + 0.2, 0.5 = 0.3 + 0.2, 0.5 = 0.3 + 0.2.

As an example of where the above solution does NOT produce a minimal |B|, let A = {{0.5, 0.5},{0.5, 0.5}}. Then the above solution gives B = {0.25, 0.25, 0.25, 0.25}, which works, but B = {0.5, 0.5} works and is smaller.

[tex]|B| = \prod_j |a_j| [/tex] by the above method. In the special case when the elements of each [tex]a_j[/tex] are all the same, it is possible to find a B where [tex]|B| = lcm(a_1, a_2, ..., a_n)[/tex] (as I did in the preceding paragraph). I believe that it is never possible to find a B where [tex]|B| < lcm(a_1, a_2, ..., a_n)[/tex], no matter what A is.
 
Mathematics news on Phys.org
  • #2
I cannot see why any requirement should prevent me from calling ##A=B## a solution.
 

Related to Solving the Multiset Filling Problem

1. What is the Multiset Filling Problem?

The Multiset Filling Problem is a mathematical problem that involves filling a multiset (a set with repeated elements) with non-negative integers while satisfying a given set of constraints. The goal is to find a solution that minimizes the sum of the filled elements.

2. Why is the Multiset Filling Problem important?

The Multiset Filling Problem has applications in various fields such as computer science, operations research, and logistics. It can be used to model real-world problems such as resource allocation, scheduling, and inventory management.

3. What are the main challenges in solving the Multiset Filling Problem?

One of the main challenges in solving the Multiset Filling Problem is finding an efficient algorithm that can handle large and complex instances. Another challenge is dealing with the exponential number of possible solutions, which makes it difficult to find the optimal solution in a reasonable amount of time.

4. What are some approaches to solving the Multiset Filling Problem?

Some common approaches to solving the Multiset Filling Problem include dynamic programming, integer programming, and heuristic methods. These methods vary in their complexity and efficiency, and the choice of approach depends on the specific problem instance and its constraints.

5. How can the Multiset Filling Problem be applied in real-world scenarios?

The Multiset Filling Problem can be applied in various real-world scenarios, such as optimizing inventory levels in supply chain management, scheduling tasks in project management, and allocating resources in telecommunications networks. It can also be used in recreational mathematics problems, such as creating magic squares with specific properties.

Similar threads

Replies
5
Views
517
Replies
6
Views
1K
Replies
3
Views
841
Replies
1
Views
3K
Replies
5
Views
1K
  • General Math
Replies
1
Views
29K
Replies
7
Views
1K
  • General Math
Replies
1
Views
4K
Replies
3
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
Back
Top