3
$\begingroup$

Imagine that you have a normalized knapsack constraint with $n$ items and weights $w_1,...,w_n$ satisfying $\sum_{i=1}^n w_i = 1$. I'm trying to understand the behavior of the function

$$Z(c) = \#| S \subset \{1,...,n\} : \sum_{i \in S} w_i \leq c|.$$

Clearly if $c = 0$, then $Z(c) = 0$, and if $c = 1$ then $Z(c) = 2^n$. Are there any results on phase transition behavior for $Z(c)$ when the $w_i$ are drawn randomly?

I'm aware there are results, for example, for counting the number of solutions to constraint satisfiability problems, but I haven't seen similar results for a counting the feasible solutions to a knpasack constraint.

$\endgroup$
2
$\begingroup$

I don't have a reference for you, just a minor remark that is too large for a comment.

We assume $w$ is chosen as follows. Choose r.v. $x\in[0,1]^n$ uniformly at random (i.e., each $x_i$ is i.i.d. uniformly in $[0,1]$), then set $w_i = x_i/X$, where $X=\sum_j x_j$. Then with high probability, almost all sets $S$ will have $\sum_{i\in S} w_i \sim 1/2$:

Lemma 1. Let r.v. $w$ be chosen as above. With probability $1-e^{-n/6}$, for all $\epsilon\in[0,1]$, among the subsets $S\subseteq\{1,\ldots,n\}$, the fraction satisfying $$\textstyle\Big|1/2 - \sum_{i\in S} w_i\Big| \ge \epsilon$$ is at most $2 e^{-n\epsilon^2/4}$.

Proof. For any $x$, and $X=\sum_{i=1}^n x_i$ as described above, note that $E[X] = n/2$, so by a standard Chernoff bound the probability of the event $X\le n/4$ is at most $e^{-n^2/6}$. So, with probability at least $1-e^{-n^2/6}$, $X\ge n/4$.

Now fix any $x$ and $w$ with $X\ge n/4$, and fix $\epsilon>0$. To complete the proof we bound the fraction of subsets $S$ such that $|1/2 - \sum_{i\in S} w_i| \ge \epsilon$.

This fraction equals the probability that $|1/2 - \sum_{i\in S} w_i| \ge \epsilon$ for a random subset $S\subseteq \{1,\ldots,n\}$.

Because $w=x/X$, the condition $|1/2 - \sum_{i\in S} w_i| \ge \epsilon$ is equivalent to $|X/2 - \sum_{i\in S} x_i| \ge \epsilon X$.

Note that $E_S[\sum_{i \in S} x_i] = X/2$, so by a standard Chernoff bound $$\Pr_S\big[|X/2 - \textstyle\sum_{i\in S} x_i| \ge \epsilon X\big] \le 2\exp(-X\epsilon^2) \le 2\exp(-n\epsilon^2/4).$$ (The last step uses $X\ge n/4$.) $~~\Box$

We don't have to choose $w$ randomly to get the bound. Any $w$ with $\max_i w_i = O(1/n)\sum_i w_i$ will do.

Note that the result implies a sharp threshold in the following sense: for any $c > 1/2$, almost all sets $S$ will satisfy the given knapsack inequality $\sum_{i\in S} x_i \le c$. For any $c < 1/2$, almost none will.

$\endgroup$

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.