Edited: Suppose we have 4 sets $A, B, C, D $ which can can hold a maximum of two elements, each.
Now, elements ($E_i$) arrive serially with properties such as:
E1 : Should be placed in either B or C. E2 : Should be placed in either A or B or C. E3 : Should be placed in either A or B.
When an element arrives, we have to place the element in one of the 4 sets, immediately i.e. we cannot wait for all elements to arrive, and then decide.
When a new element arrives:
- If there exists space in one or more sets, satisfying the constraints, we place the element in the set with minimum cardinality. Ties are broken randomly.
- If there is no space satisfying the constraints, the existing elements may be redistributed to accommodate the new element.
- If even after redistribution, there is no space satisfying the constraints, discard the new element.
Objective Accommodate the newly arriving elements, while having less number of redistribution.
What strategy should i choose to achieve the objective? I need an algorithm for the redistributions that is scalable to large number of sets and more than 2 entry for each set.
In the picture, randomly I have chosen 2 possibilities, one of which yields less number of redistribution than the other. So are there any approaches other than exhaustively checking all possible combinations?