Distributing objects on containers
$begingroup$
Suppose we have $n$ containers, each has the ability of holding $f_{i}$ object for $i=1, 2, dots, n$. That means $f_{i}$ is the maximum number of object that the $i$th container can hold.
Now, we have $N$ objects in total. We assume that $displaystyle sum_{i=1}^{n} f_{i} > N$ such that all $N$ objects can actually be filled into the containers.
Question:
How to distribute these objects to the containers such that each container would not reach to its upper limit too quickly?
If $f_{i} equiv f$ for all $i$, then my intuition told me that the $N$ objects must be uniformly distributed to the containers. (seems related to entropy). But what if all $f_{i}$ are different? What is the objective function?
optimization entropy
asked Jan 9 at 6:22
K_inverseK_inverse
273213
$endgroup$
add a comment |
$begingroup$
Suppose we have $n$ containers, each has the ability of holding $f_{i}$ object for $i=1, 2, dots, n$. That means $f_{i}$ is the maximum number of object that the $i$th container can hold.
Now, we have $N$ objects in total. We assume that $displaystyle sum_{i=1}^{n} f_{i} > N$ such that all $N$ objects can actually be filled into the containers.
Question:
How to distribute these objects to the containers such that each container would not reach to its upper limit too quickly?
If $f_{i} equiv f$ for all $i$, then my intuition told me that the $N$ objects must be uniformly distributed to the containers. (seems related to entropy). But what if all $f_{i}$ are different? What is the objective function?
optimization entropy
asked Jan 9 at 6:22
K_inverseK_inverse
273213
$endgroup$
add a comment |
$begingroup$
Suppose we have $n$ containers, each has the ability of holding $f_{i}$ object for $i=1, 2, dots, n$. That means $f_{i}$ is the maximum number of object that the $i$th container can hold.
Now, we have $N$ objects in total. We assume that $displaystyle sum_{i=1}^{n} f_{i} > N$ such that all $N$ objects can actually be filled into the containers.
Question:
How to distribute these objects to the containers such that each container would not reach to its upper limit too quickly?
If $f_{i} equiv f$ for all $i$, then my intuition told me that the $N$ objects must be uniformly distributed to the containers. (seems related to entropy). But what if all $f_{i}$ are different? What is the objective function?
optimization entropy
asked Jan 9 at 6:22
K_inverseK_inverse
273213
$endgroup$
Suppose we have $n$ containers, each has the ability of holding $f_{i}$ object for $i=1, 2, dots, n$. That means $f_{i}$ is the maximum number of object that the $i$th container can hold.
Now, we have $N$ objects in total. We assume that $displaystyle sum_{i=1}^{n} f_{i} > N$ such that all $N$ objects can actually be filled into the containers.
Question:
How to distribute these objects to the containers such that each container would not reach to its upper limit too quickly?
If $f_{i} equiv f$ for all $i$, then my intuition told me that the $N$ objects must be uniformly distributed to the containers. (seems related to entropy). But what if all $f_{i}$ are different? What is the objective function?
optimization entropy
optimization entropy
asked Jan 9 at 6:22
K_inverseK_inverse
273213
asked Jan 9 at 6:22
K_inverseK_inverse
273213
edited Jan 9 at 6:39
K_inverse
asked Jan 9 at 6:22
K_inverseK_inverse
273213
asked Jan 9 at 6:22
K_inverseK_inverse
273213
asked Jan 9 at 6:22
K_inverseK_inverse
273213
273213
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
If you want to maximize the time until any bin reaches its maximum limit.
At any moment of time, when we want to insert an object, look for a bin with at least $2$ slots left.
That way, if $Nle sum_{i=1}^nf_i-n-1$, the upper limit for every bin is not attained.
If $N ge sum_{i=1}^nf_i-n$, then we don't have a choice but let one of the bin attain the maximum.
answered Jan 9 at 7:09
Siong Thye GohSiong Thye Goh
100k1465117
$endgroup$
$begingroup$
How did you obtain the inequality constraint?
$endgroup$
– K_inverse
Jan 9 at 7:40
$begingroup$
Intuitively, when we have too many objects, we have no choice but to hit an upper limit. Now, the question is what is having too many objects. My proposed strategy is to avoid hitting any upper limit whenever we can. The first moment when we can't avoid is when every bins has exactly $1$ slot left. Total number of slots is $sum_{i=1}^n f_i$, and the number of bins is $n$.
$endgroup$
– Siong Thye Goh
Jan 9 at 8:02
$begingroup$
Thanks. Apart from just avoiding hitting the upper limit, I would like to distribute the objects such that every containers would have enough buffer. Not sure what are the keys word to search for this problem. My feeling is that it is related to entropy, but I am not sure.
$endgroup$
– K_inverse
Jan 9 at 11:45
$begingroup$
would have enough buffer? is it that some objects must go to certain bins only?
$endgroup$
– Siong Thye Goh
Jan 9 at 12:28
$begingroup$
well yes, there are some constraints on what are the available containers for each object. But I tried to ignore these constraints first for simplicity.
$endgroup$
– K_inverse
Jan 9 at 12:43
|
show 2 more comments
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3067149%2fdistributing-objects-on-containers%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
If you want to maximize the time until any bin reaches its maximum limit.
At any moment of time, when we want to insert an object, look for a bin with at least $2$ slots left.
That way, if $Nle sum_{i=1}^nf_i-n-1$, the upper limit for every bin is not attained.
If $N ge sum_{i=1}^nf_i-n$, then we don't have a choice but let one of the bin attain the maximum.
answered Jan 9 at 7:09
Siong Thye GohSiong Thye Goh
100k1465117
$endgroup$
$begingroup$
How did you obtain the inequality constraint?
$endgroup$
– K_inverse
Jan 9 at 7:40
$begingroup$
Intuitively, when we have too many objects, we have no choice but to hit an upper limit. Now, the question is what is having too many objects. My proposed strategy is to avoid hitting any upper limit whenever we can. The first moment when we can't avoid is when every bins has exactly $1$ slot left. Total number of slots is $sum_{i=1}^n f_i$, and the number of bins is $n$.
$endgroup$
– Siong Thye Goh
Jan 9 at 8:02
$begingroup$
Thanks. Apart from just avoiding hitting the upper limit, I would like to distribute the objects such that every containers would have enough buffer. Not sure what are the keys word to search for this problem. My feeling is that it is related to entropy, but I am not sure.
$endgroup$
– K_inverse
Jan 9 at 11:45
$begingroup$
would have enough buffer? is it that some objects must go to certain bins only?
$endgroup$
– Siong Thye Goh
Jan 9 at 12:28
$begingroup$
well yes, there are some constraints on what are the available containers for each object. But I tried to ignore these constraints first for simplicity.
$endgroup$
– K_inverse
Jan 9 at 12:43
|
show 2 more comments
$begingroup$
If you want to maximize the time until any bin reaches its maximum limit.
At any moment of time, when we want to insert an object, look for a bin with at least $2$ slots left.
That way, if $Nle sum_{i=1}^nf_i-n-1$, the upper limit for every bin is not attained.
If $N ge sum_{i=1}^nf_i-n$, then we don't have a choice but let one of the bin attain the maximum.
answered Jan 9 at 7:09
Siong Thye GohSiong Thye Goh
100k1465117
$endgroup$
$begingroup$
How did you obtain the inequality constraint?
$endgroup$
– K_inverse
Jan 9 at 7:40
$begingroup$
Intuitively, when we have too many objects, we have no choice but to hit an upper limit. Now, the question is what is having too many objects. My proposed strategy is to avoid hitting any upper limit whenever we can. The first moment when we can't avoid is when every bins has exactly $1$ slot left. Total number of slots is $sum_{i=1}^n f_i$, and the number of bins is $n$.
$endgroup$
– Siong Thye Goh
Jan 9 at 8:02
$begingroup$
Thanks. Apart from just avoiding hitting the upper limit, I would like to distribute the objects such that every containers would have enough buffer. Not sure what are the keys word to search for this problem. My feeling is that it is related to entropy, but I am not sure.
$endgroup$
– K_inverse
Jan 9 at 11:45
$begingroup$
would have enough buffer? is it that some objects must go to certain bins only?
$endgroup$
– Siong Thye Goh
Jan 9 at 12:28
$begingroup$
well yes, there are some constraints on what are the available containers for each object. But I tried to ignore these constraints first for simplicity.
$endgroup$
– K_inverse
Jan 9 at 12:43
|
show 2 more comments
$begingroup$
If you want to maximize the time until any bin reaches its maximum limit.
At any moment of time, when we want to insert an object, look for a bin with at least $2$ slots left.
That way, if $Nle sum_{i=1}^nf_i-n-1$, the upper limit for every bin is not attained.
If $N ge sum_{i=1}^nf_i-n$, then we don't have a choice but let one of the bin attain the maximum.
answered Jan 9 at 7:09
Siong Thye GohSiong Thye Goh
100k1465117
$endgroup$
If you want to maximize the time until any bin reaches its maximum limit.
At any moment of time, when we want to insert an object, look for a bin with at least $2$ slots left.
That way, if $Nle sum_{i=1}^nf_i-n-1$, the upper limit for every bin is not attained.
If $N ge sum_{i=1}^nf_i-n$, then we don't have a choice but let one of the bin attain the maximum.
answered Jan 9 at 7:09
Siong Thye GohSiong Thye Goh
100k1465117
answered Jan 9 at 7:09
Siong Thye GohSiong Thye Goh
100k1465117
answered Jan 9 at 7:09
Siong Thye GohSiong Thye Goh
100k1465117
answered Jan 9 at 7:09
Siong Thye GohSiong Thye Goh
100k1465117
100k1465117
$begingroup$
How did you obtain the inequality constraint?
$endgroup$
– K_inverse
Jan 9 at 7:40
$begingroup$
Intuitively, when we have too many objects, we have no choice but to hit an upper limit. Now, the question is what is having too many objects. My proposed strategy is to avoid hitting any upper limit whenever we can. The first moment when we can't avoid is when every bins has exactly $1$ slot left. Total number of slots is $sum_{i=1}^n f_i$, and the number of bins is $n$.
$endgroup$
– Siong Thye Goh
Jan 9 at 8:02
$begingroup$
Thanks. Apart from just avoiding hitting the upper limit, I would like to distribute the objects such that every containers would have enough buffer. Not sure what are the keys word to search for this problem. My feeling is that it is related to entropy, but I am not sure.
$endgroup$
– K_inverse
Jan 9 at 11:45
$begingroup$
would have enough buffer? is it that some objects must go to certain bins only?
$endgroup$
– Siong Thye Goh
Jan 9 at 12:28
$begingroup$
well yes, there are some constraints on what are the available containers for each object. But I tried to ignore these constraints first for simplicity.
$endgroup$
– K_inverse
Jan 9 at 12:43
|
show 2 more comments
$begingroup$
How did you obtain the inequality constraint?
$endgroup$
– K_inverse
Jan 9 at 7:40
$begingroup$
Intuitively, when we have too many objects, we have no choice but to hit an upper limit. Now, the question is what is having too many objects. My proposed strategy is to avoid hitting any upper limit whenever we can. The first moment when we can't avoid is when every bins has exactly $1$ slot left. Total number of slots is $sum_{i=1}^n f_i$, and the number of bins is $n$.
$endgroup$
– Siong Thye Goh
Jan 9 at 8:02
$begingroup$
Thanks. Apart from just avoiding hitting the upper limit, I would like to distribute the objects such that every containers would have enough buffer. Not sure what are the keys word to search for this problem. My feeling is that it is related to entropy, but I am not sure.
$endgroup$
– K_inverse
Jan 9 at 11:45
$begingroup$
would have enough buffer? is it that some objects must go to certain bins only?
$endgroup$
– Siong Thye Goh
Jan 9 at 12:28
$begingroup$
well yes, there are some constraints on what are the available containers for each object. But I tried to ignore these constraints first for simplicity.
$endgroup$
– K_inverse
Jan 9 at 12:43
$begingroup$
How did you obtain the inequality constraint?
$endgroup$
– K_inverse
Jan 9 at 7:40
$begingroup$
How did you obtain the inequality constraint?
$endgroup$
– K_inverse
Jan 9 at 7:40
$begingroup$
Intuitively, when we have too many objects, we have no choice but to hit an upper limit. Now, the question is what is having too many objects. My proposed strategy is to avoid hitting any upper limit whenever we can. The first moment when we can't avoid is when every bins has exactly $1$ slot left. Total number of slots is $sum_{i=1}^n f_i$, and the number of bins is $n$.
$endgroup$
– Siong Thye Goh
Jan 9 at 8:02
$begingroup$
Intuitively, when we have too many objects, we have no choice but to hit an upper limit. Now, the question is what is having too many objects. My proposed strategy is to avoid hitting any upper limit whenever we can. The first moment when we can't avoid is when every bins has exactly $1$ slot left. Total number of slots is $sum_{i=1}^n f_i$, and the number of bins is $n$.
$endgroup$
– Siong Thye Goh
Jan 9 at 8:02
$begingroup$
Thanks. Apart from just avoiding hitting the upper limit, I would like to distribute the objects such that every containers would have enough buffer. Not sure what are the keys word to search for this problem. My feeling is that it is related to entropy, but I am not sure.
$endgroup$
– K_inverse
Jan 9 at 11:45
$begingroup$
Thanks. Apart from just avoiding hitting the upper limit, I would like to distribute the objects such that every containers would have enough buffer. Not sure what are the keys word to search for this problem. My feeling is that it is related to entropy, but I am not sure.
$endgroup$
– K_inverse
Jan 9 at 11:45
$begingroup$
would have enough buffer? is it that some objects must go to certain bins only?
$endgroup$
– Siong Thye Goh
Jan 9 at 12:28
$begingroup$
would have enough buffer? is it that some objects must go to certain bins only?
$endgroup$
– Siong Thye Goh
Jan 9 at 12:28
$begingroup$
well yes, there are some constraints on what are the available containers for each object. But I tried to ignore these constraints first for simplicity.
$endgroup$
– K_inverse
Jan 9 at 12:43
$begingroup$
well yes, there are some constraints on what are the available containers for each object. But I tried to ignore these constraints first for simplicity.
$endgroup$
– K_inverse
Jan 9 at 12:43
|
show 2 more comments
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3067149%2fdistributing-objects-on-containers%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
