Groups that cover weighted set

Question

I am trying to find an efficient algorithm to give solutions to the following problem.

There is a set of unknown groups of elements $g_1$, $g_2$, $g_3$, etc. that together contain and cover a set of elements $e_1$, $e_2$, $e_3$, $\ldots$ These groups share elements. Each element has associated a value between $0$ and $1$. So for example $e_1 = 0.4$ and $e_4 = 0.4$. Each group has associated a value from $0$ to $1$. So for example, $g_1 = 0.1$ and $g_3 = 0.4$. The group weights sum to $1$. That is $g_1 + g_2 + g_3 + \ldots = 1$.

I want to find the groups $g_1$, $g_2$, $\ldots$ and their respective weights such that

$$\sum_{\left\{i \,\mid\, e_j \in g_i\right\}} g_i = e_j$$

Mathematically speaking, if $E$ is a vector of the elements weights and $G$ is a vector of groups weights then I want to find a $0-1$ matrix $W$ and a positive real matrix $G$ such that $E = W G$ and $\textrm{sum}(G) = 1$

Going a bit further... If $E$ is now a matrix of elements values between $0$ and $1$, can I find a real positive matrix $G$ such that each column sums to $1$ and a $0-1$ matrix $W$ such that $E = W G$?

Answer 1

The first part is easy: suppose without loss of generality that $e_0 \le e_1 \le \ldots \le e_n$. Then let

• $g_1 = \{ e_1, e_2, \ldots, e_n \}$ with weight $e_1$,
• $g_2 = \{ e_2, e_3, \ldots, e_n \}$ with weight $(e_2 - e_1)$,
• $\vdots$
• $g_{n+1} = \{ \}$ with weight $(1 - e_n)$

Note that this requires one more group than element. It can't be solved in general if the number of groups must be the same as the number of elements: an easy counterexample is the case with exactly one element $e$ where its weight is not $0$ or $1$.