I am trying to properly catalog a type of partition problem I have defined. I would like to know the name of these type of problems so I can do some more research. Initially I think that it might be referred as follows:
Partition Problem > multi-way partition problem
Which is defined as (Wikipedia) "the optimization version of the partition problem. Here, the goal is to divide a set or multiset of $n$ integers into a given number $k$ of subsets, minimizing the difference between the smallest and the largest subset sums."
For that reason I am using as a lead paper to gather ideas: "Korf, Richard E. (2009). Multi-Way Number Partitioning (PDF). IJCAI."
Specially the introduction states that
"...the number partitioning problem is to divide them into a collection of mutually exclusive and collectively exhaustive subsets so that the sum of the numbers in each subset are as nearly equal as possible."
But I am not really sure if my defined problem could be included in that kind of generic problems. Here is the description / algorithm of the problem:
Initially there is a FIFO set $F$ and an empty list $S$ of subsets. Every time a subset is generated it will have an index $i$, for instance $S_i$. The first subset will be $S_0$, then $S_1$, etc. The main rule is that in every moment the sum of the elements of any $S_j$ will be smaller or equal to the sum of the elements of any $S_i$ with an index $i$ smaller than $j$.
Take the head element of the FIFO set and
a) If the sum of the elements of the subset with greatest index $S_k$ is greater or equal to the new element, then create a new subset $S_{k+1}$ and insert the element.
b) If not, then insert the element in the existing subset $S_j$ with the greatest possible index $j$ such as when the element is aggregated the sum of the subset $S_j$ is still smaller or equal than any sum of any subset $S_i$ with lower index $i$ than $j$. If no subset with index greater than $0$ complies with the rule, then the element is inserted into $S_0$ (if $S_0$ still was not generated, it is created and then the element is inserted).
- Repeat from step $2$ until the FIFO set is empty.
After some repetitions of this algorithm, the subsets look like this:
The first generated subset, $S_0$, is the one on the top, them the $S_1$ is below, and so on. The previously generated subsets will always have a sum greater or equal than any other lately generated subsets. There are two interesting subsets there, $S_0$ and the set of first elements of each $S_i$, I will call it $F$.
$S_0=\{1,2,4,5,8,12,17,19...\}$. $S_0$ will always be the subset with the greatest value of the sum of its elements.
$F=\{1,3,7,11,16,25...\}$. The elements of this subset are those elements of the initial FIFO set capable of forcing the generation of a new subset.
Tried to find them at OEIS, but unluckily they are not included.
I would like to ask the following questions:
How could I catalog this kind of subset problem? Is it valid to assimilate a FIFO as a set?
If it can not be cataloged as a subset problem, is there another kind of problems managing this kind of models?
UPDATE (2016/5/16): to understand better the problem I have tried to do an easier version in which there is a restriction in the quantity of subsets that can be generated: only two subsets are allowed, $S_0$ and $S_1$. Applying the algorithm the result after some iterations is as follows:
And fortunately for this version there is some information at OEIS! The elements marked in the first subset ($S_0$, upper subset) are exactly the sequence A007051. So the subsets for a $2$-subset problem can be obtained by calculation of that sequence.