0
$\begingroup$

Suppose we have 3 sets $A, B, C$ which can can hold a maximum of two elements, each. So the total number of elements that the sets can hold together i.e. total capacity (TC) is $ 3*2 = 6$.

Now, elements arrive serially (one-by-one) with some properties that impose the following constraints:

E1 : Can be placed in either A or B but not C.
E2 : Can be placed in either B or C but not A.
E3 : Can be placed in either A or C but not B.
E4 : Can be placed in only B.

Given that we have no prior knowledge about these elements, the challenge is to distribute these elements into the sets $A, B, C$ such that the properties are satisfied.

Here we can see that the total number of incoming elements are $4$ and TC is $6$.

Assumption : There always exists a feasible solution

Question : What algorithmic approach is appropriate for this situation? Again I stress that we have no apriori knowledge about the elements.

$\endgroup$
  • $\begingroup$ Can you wait to decide which set to put an element into, until after you see all of the constraints? Or do you have to decide when the element arrives? When the element arrives, do you see only its constraint (and none of the other constraints for later-arriving elements)? What approaches have you tried? The obvious is brute force. There is no approach that will guarantee to pick a valid distribution on the fly (even if in retrospect we know one exists after seeing all the constraints). What do you want to do about that? $\endgroup$ – D.W. Feb 12 '18 at 8:03
  • $\begingroup$ No, we cannot wait for all the elements to arrive. We have to insert the elements on arrival (considering the current state of the sets). My idea is: Upon arrival of an element, we look at the constraints and if the element can be placed in more than one set , we choose the one with the minimum cardinality. If it can be placed in only one set, we place it if space exists, otherwise give up. My intention is to insert the maximum number of elements possible, altogether. The elements can be redistributed among the sets on arrival considering the constraints. What would be the best approach? $\endgroup$ – Niloy Saha Feb 12 '18 at 11:03
1
$\begingroup$

There's no way to guarantee that you will find such an assignment, if you have to do it on the fly.

For example, suppose E1's constraint is "Can be placed in either A or B but not C". Now you decide which set you want to put it into (A or B).

  • If you decide A, maybe E2's constraint will be "Can only be placed in A" and E3's constraint will be "Can only be placed in A" and you are hosed. At that point there's no way you can satisfy all the constraints (even though in retrospect there does exist a way to satisfy the constraints, there's no way to reach it once you decide to put E1 into A).

  • If you decide E1 goes into B, maybe E2's constraint will be "Can only be placed in B" and E3's constraint will be "Can only be placed in B" and you are still hosed. You are stuck and won't be able to satisfy all the constraints.

Of course, at the time you see E1, you don't know which one of those situations it will turn out to be. So no matter what you pick after seeing the constraint for E1, there's a chance you will end up stuck. You cannot guarantee to always find such an assignment -- not even if you are promised that one exists.

If you knew all of the constraints before having to make any selections, then it would be feasible (e.g., brute force suffices). But that doesn't work on the fly.

This is an example of what's known as an "adversarial argument": no matter what choice your algorithm makes, an adversary can always arrange to screw you over.

$\endgroup$
  • $\begingroup$ If the existing elements can be redistributed (when a new element arrives) to achieve better utilisation considering the constraints, what approach would minimise the number of such redistribution operations? Even if the solution cannot be guaranteed, what approach would give me near optimal solution? $\endgroup$ – Niloy Saha Feb 12 '18 at 11:06
  • $\begingroup$ @NiloySaha, that's a different question, and one that should be posted separately using the 'Ask Question' button, rather than asking in the comments. Make sure to state all your requirements in the original post. This site doesn't work well for interactive conversations or back-and-forth. $\endgroup$ – D.W. Feb 12 '18 at 16:29
  • $\begingroup$ Okay, thanks! I've marked your answer as the solution. $\endgroup$ – Niloy Saha Feb 12 '18 at 17:09

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.