6
$\begingroup$

We are given a constant $B \geq 3$, a set of positive integers $I$ s.t. $\forall i \in I, i \leq B$ and $\sum_{i \in I} = N$, and 2) a packing of these numbers into $N/B > 1$ bins of size $B$.

An adversary replaces two numbers with their addition so that a packing exists. I.e., for some $i,j \in I, i+j \leq B$, the set $I' = (I \setminus \{i,j\}) \cup \{i+j\}$ admits a packing into $N/B$ bins.

An optimal update minimizes the number of touched bins during the re-packing for $I'$. We are interested in the maximum number of bins an optimal update would touch.

Questions: How many bins (at most) an optimal update has to touch in a worst case?

Does it depend on the number of bins or it is some function of only $B$?

$\endgroup$
5
$\begingroup$

We can show there's an upper bound based only on B.

Fix B, then i and j. Let the tuple $(x_{1}, \dots, x_{k}) \in \mathbb{N}_{\geq 0}^{k}$ denote the packing where we have $x_{t}$ bins of type $t$, where the type of a bin is just the numbers that are packed in it. We have the trivial upper bound $k \leq 2^{B-1}$.

Let $f(x_{1}, \dots, x_{k}) : \mathbb{N}_{\geq 0}^{k} \mapsto \mathbb{N}_{\geq 0} \cup \infty$ be a function mapping any packing into the minimum number of bins we have to touch, with $f = \infty$ if there exists no repacking. Clearly $f(y_{1}, \dots, y_{k}) \geq f(x_{1}, \dots, x_{k})$ when $y_{t} \leq x_{t}$ for all $t$, since any repacking we can do with $Y$ we can also do with $X$.

Now define $S = \{(x_{1}, \dots, x_{k}) \in \mathbb{N}_{\geq 0}^{k} \mid f(x_{1}, \dots, x_{k}) < \infty\}$. This is a set of $k$-tuples of nonnegative integers, therefore by Dickson's lemma it has only finitely many minimal elements, where an element $X = (x_{1}, \dots, x_{k}) \in S$ is minimal if there exists no other element $Y = (y_{1}, \dots, y_{k}) \in S$ such that $y_{t} \leq x_{t}$ for all $t$. Let $H_{i, j}$ be the maximum value of $f$ over the minimal elements. As the maximum of a finite number of finite elements, it is finite.

Now for any $X = (x_{1}, \dots, x_{k}) \in S$ there exists minimal $Y = (y_{1}, \dots, y_{k}) \in S$ such that $y_{t} \leq x_{t}$ for all $t$, but then $f(x_{1}, \dots, x_{k}) \leq f(y_{1}, \dots, y_{k}) \leq H_{i, j}$. Therefore if $f$ is finite it is at most $H_{i, j}$.

Therefore $\max_{i, j} H_{i, j}$ is an upper bound on the number of bins we need to touch, and it depends only on $B$. As the maximum of a finite number of finite elements, it is finite.

$\endgroup$
  • $\begingroup$ Thanks for the interesting argument. It is not convincing though. The objective is to show that $f$ does not grow with $N$ and it depends only on $B$. The weaker version that you considered is also interesting: $f$ is finite when $N \to \infty$. At the beginning you assume $f$ is finite whenever there exists a packing. You conclude, if $f$ is finite then it is a function of $B$. Isn't this conclusion trivial when you already assumed $f$ is finite? We want to show $f$ is always finite even with infinite number of bins. $\endgroup$ – Parham Oct 11 '19 at 13:53
  • 1
    $\begingroup$ So the question was not to prove an upper bound based only on B, but to show that the exact worst case amount we have to touch is based only on B? Clearly N has to affect the exact amount, since for $N = B$ we touch one, for $N = 2B$ we might need to touch two. The former was proven here though, if repacking is possible we always need to touch at most $\max_{i, j} H_{i, j}$ bins to do it, which is a finite value depending only on $B$, not on $N$. Furthermore it is an upper bound even if we allow $N = \infty$, just replace $\mathbb{N}_{\geq 0}^{k}$ with $(\mathbb{N}_{\geq 0} \cup \infty)^{k}$. $\endgroup$ – Antti Röyskö Oct 12 '19 at 23:04
  • $\begingroup$ @Antti I don't get the last sentence. In the finite case, we know that if there is a packing, there is also a finite repacking (pack everything out, then back). But for infinitely many bins this might not hold. $\endgroup$ – domotorp Oct 28 '19 at 22:01
  • $\begingroup$ Indeed, suppose that B=3 and our numbers are 1's and 2's, such that in each bin we have a 1 and a 2. If two 1's are merged, then an infinite repacking is needed. Of course, this question is quite unrelated to the original problem. $\endgroup$ – domotorp Oct 28 '19 at 22:19
  • 2
    $\begingroup$ @domotorp An infinite repacking is undefined and a repacking is always a finite process. So when we assume infinite number of bins, any worst case repacking is trivially finite. In the case of your example, a repacking simply doesn't exist. $\endgroup$ – Parham Oct 29 '19 at 12:37

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.