Random Walks on Truncated Cubes and Sampling 0-1 Knapsack Solutions.
We solve an open problem concerning the mixing time of symmetric random walk on the n-dimensional cube truncated by a hyperplane, showing that it is polynomial in n.  As a consequence, we obtain a fully polynomial randomized approximation scheme for counting the feasible solutions of a 0-1 knapsack problem. The results extend to the case of any fixed number of hyperplanes. The key ingredient in our analysis is a combinatorial construction we call a "balanced almost uniform permutation," which is of independent interest.
Introduction
For a positive real vector a
and real number b,
let
denote the set of 0-1 vectors
for which
a  x
a
Geometrically, we can
view
as the set of vertices of the n-dimensional cube f0; 1g n which lie on
one side of the hyperplane a
Combinatorially,
is the set of feasible solutions to the 0-1
knapsack problem dened by a and b: if we think of the a i as the weights of a set of n items, and
b as the capacity (weight limit) of a knapsack, then there is a 1-1 correspondence between vectors
xand subsets of items X whose aggregated weight does not exceed the knapsack capacity,
given by 1g. We shall write a(X) for the weight of X, i.e.,
i2X a i .
This paper is concerned with the problem of computing
i.e., counting the number of feasible
solutions to the knapsack problem. The problem is #P-complete in exact form, so we aim for a good
approximation algorithm, specically a fully-polynomial randomized approximation scheme (fpras).
By a well-known relationship based on self-reducibility [12, 11], this is equivalent to constructing a
polynomial time algorithm for sampling elements
of
(almost) uniformly at random.
In recent years there has been a steady stream of results of this kind for #P-complete counting
problems (see, for example, [13, 11, 8] for surveys); however, the 0-1 knapsack problem still stands
A preliminary version of this paper appeared in Proceedings of the 40th IEEE Symposium on Foundations of
Computer Science, October 1999, pp. 230{240.
y Department of Statistics, Evans Hall, University of California, Berkeley CA 94720. Email:
morris@stat.berkeley.edu. Supported by NSF graduate and post-doctoral fellowships and by NSF grant ECS-
9873086.
z Computer Science Division, Soda Hall, University of California, Berkeley CA 94720-1776. Email:
sinclair@cs.berkeley.edu. Supported in part by NSF grants CCR-9505448 and CCR-9820951.
as one of a small handful of canonical problems that have so far resisted attack. Indeed, it has been
quoted as an open problem in several places [4, 11, 13, 15]. This interest stems in part from its
combinatorial signicance and its appealing geometric structure, and in part from the challenge it
poses to existing methods. In this paper, we resolve this issue by constructing an fpras for the 0-1
knapsack problem. Along the way we introduce some new machinery that we believe will be useful
for tackling other problems of a similar
avor, and possibly beyond.
Almost all known approximate counting algorithms proceed by simulating a suitable random
walk on the set of
interest
. The walk is constructed so that it converges to the uniform distribution
over
simulation of the walk for su-ciently many steps therefore allows one to sample (almost)
uniformly
from
, and thus to approximate
j. In any application of this method, the key step
is to establish that the random walk is rapidly mixing, i.e., gets close to the uniform distribution
after a polynomial number of steps.
In the case of 0-1 knapsack solutions, a particularly simple and natural random walk
on
has
been proposed. If the current state is X
1. pick an item i ng uniformly at random (u.a.r.);
2. if i 2 X, move to X fig; if
move to X [ fig; otherwise, do
nothing.
This process may equivalently be viewed as a nearest neighbor random walk on the portion of the
cube f0; 1g n truncated by the hyperplane a  in which the probability of moving to any
neighbor is 1
will call this graph
G
. To avoid technical issues involving periodicity, we add
to every state a holding probability of 1: i.e., with probability 1do nothing, else make a move as
described above.
It is easy to check that this random walk converges to the uniform distribution
over
. However,
despite much recent activity in the analysis of mixing times of random walks, this deceptively simple
example is still not known to be rapidly mixing. There is strong geometric intuition that it should
be: random walk on the entire cube f0; 1g n is rapidly mixing, and truncation by a hyperplane
presumably cannot create \bottlenecks" that would severely slow down convergence. Nonetheless,
the best known bound on the mixing time remains exp(O( p n(log n) 5=2 )) [4], which beats the trivial
bound of exp(O(n)) but is still exponential.
In this paper we prove that the above random walk is indeed rapidly mixing, with a mixing time
of O(n 9=2+ ) steps for any  > 0. This immediately implies the existence of an fpras for counting
knapsack solutions.
We also present a non-trivial extension of these results to the case of multiple hyperplanes (more
precisely, multiple constraints of the form a j  x  b j for non-negative vectors a j ). 1 Here we are also
able to prove a mixing time of O(n c ) (where c is a constant) for any xed number of hyperplanes.
(The exponent c depends on the number d of hyperplanes, but this is inevitable as it is not hard
to prove a lower bound of n
d) on the mixing time. Moreover, it is possible to encode NP-hard
problems if the number of hyperplanes is permitted to depend on n, so we would not expect any
polynomial time sampling algorithm for this case.)
To prove rapid mixing we use a technique based on multicommodity
ow (see [16]): if we can
route unit
ow between each pair of vertices X;Y in
G
simultaneously in such a way that no edge
carries too much
ow, then the random walk is rapidly mixing. This technique is well known, but
most previous applications (e.g., [9, 10]) have made use of \degenerate"
ows in which all
We mention in passing that all our results extend from the 0-1 case to more general cubes of the form
This extension is purely technical and does not require any substantial new ideas, so we omit the details.
ow is routed along a single canonical path (though see [1, 16] for exceptions). Our analysis seems
to rely essentially on spreading out the
ow along multiple paths.
The key ingredient in our analysis is the specication of these paths, which we achieve via an
auxiliary combinatorial construction that we believe is of independent interest and will nd further
applications elsewhere. Note that a shortest path between a pair of vertices X;Y of
G
can be
viewed as a permutation of the symmetric dierence X  Y , the set of items that must be added
to or removed from the knapsack in passing from X to Y . A natural approach to dening a good
ow is to use a random permutation, so that the
ow is spread evenly among all shortest paths
and no edge is overloaded. However, a fundamental problem with this approach is that a random
permutation will tend to violate the knapsack constraint, as too many items will have been added
at some intermediate point. Slightly less obviously, a symmetric problem arises because a random
permutation will tend to remove too many items at some intermediate point, causing congestion
among edges of the hypercube near the origin. To avoid these problems, we want our permutations
to remain \balanced," in the sense that items are added and removed at approximately the correct
rates throughout the path; but we also want them to be \su-ciently random" to ensure a well
spread
ow. More specically, it turns out that we require the distribution of the initial segment
viewed as an unordered set, to be \almost uniform." We call permutations with
these properties balanced almost uniform permutations. A main contribution of this paper is to
show the existence of such permutations.
The remainder of this paper is structured as follows. We begin with some necessary background
on
ows and rapid mixing in section 2. We then establish rapid mixing of the knapsack random
walk in the technically simpler case when the item weights a i lie in the range [1; B], for some
constant B. This analysis is in two parts: in section 3 we show how to construct balanced almost
uniform permutations, and in section 4 how to use these to dene a good
ow. We then extend
everything to the general case in section 6. The extension to multiple constraints is handled in
section 6; this involves extending our construction of balanced almost uniform permutations from
scalar weights to vectors in arbitrary dimension. This again may be of independent interest.
2 The mixing time and multicommodity
ow
As indicated earlier, we will view elements
of
either as 0-1 vectors
commonly,
as subsets X  under the equivalence 1g. Recall that
i2X a i
is the weight of X, so
that
bg. Without loss of generality, we will assume that
a i  b for all i.
We consider the symmetric random walk on the portion
G
of the hypercube f0; 1g n dened in
the

Introduction

. This walk is connected (all states communicate via the zero vector) and aperiodic
(because of the holding probabilities), and since the transition probabilities are symmetric, the
distribution at time t converges to the uniform distribution
over
as regardless of the
initial state. Our goal is to bound the rate of convergence as measured by the mixing time, dened
as
min
is the initial state, P t is the distribution of the walk at time t, U is the uniform distribution
over
, and k  k denotes variation distance. 2 Thus  mix is the number of steps required, starting
from any initial state, to get the variation distance from the uniform distribution down to 1
4 . By
2 For probability distributions ;
on
, the variation distance is dened as
standard facts about geometric convergence, O( mix log  1 ) steps su-ce to reduce the variation
distance to any desired .
Fairly standard techniques (see [16]) allow us to estimate  mix by setting up a suitable multi-
commodity
ow on the underlying graph
G
. Our task is to route one unit of
ow from X to Y ,
for each ordered pair of vertices X;Ysimultaneously. For any such
ow f , and any oriented
edge e in
G
, let f(e) denote the total
ow along e; i.e., f(e) is the sum over all ordered pairs
X;Y of the
ow carried by e. Dene
e f(e), the maximum
ow along any
edge normalized by
j, and L(f) to be the length of a longest
ow-carrying path. The following
theorem 3 is a special case of results in [16] (see also [3, 2]):
Theorem 2.1 [16] For any
ow f , the mixing time is bounded by  mix  4n(n
We will bound  mix by constructing a
ow with small values of C and L. To bring out the main
conceptual ideas, we will focus initially on what we term the bounded ratio case, where all weights a i
lie in the range [1; B] for some constant B. We will derive a bound of the form
this case. By introducing some additional technical complications, we will go on to get a uniform
bound of  for the general case, for any  > 0.
Remark: We note that our bound on the mixing time is only slightly larger than the upper bound of
O(n 3 ) which one obtains by applying Theorem 2.1 to the hypercube itself (without the hyperplane
see, e.g., [17]. This is in turn somewhat o from the true mixing time of O(n log n).
On the other hand, it is fairly easy to obtain a lower bound of
log n) for the mixing time
of the truncated cube: consider, for example, an instance in which log n items have weight 1, the
other n log n items have weight n, and the knapsack capacity is
As explained in the Introduction, our
ow will be based on the idea of a balanced almost uniform
permutation. We devote the next section to this topic and then return to the knapsack random
walk in section 4.
Balanced almost uniform permutations
We begin by dening the notions of \balanced" and \almost uniform" permutations. We will write
Sm to denote the set of all permutations of
Denition 3.1 Let fw
be a set of real (not necessarily positive) weights, with
and
permutation  2 Sm is balanced if, for every k with 1  k  m,
Thus a balanced permutation is one whose partial sums do not
uctuate widely. In particular, if
Denition 3.2 Let  be a random permutation in Sm , and let  2 R. We call  a -uniform
permutation if
for every k with 1  k  m and every U  of cardinality k. (Here
the initial segment
3 We note that this theorem applies to symmetric random walk on any connected subgraph of the hypercube f0; 1g n ,
in which transitions are made to each neighbor with probability 1
Note that, if  were a uniform random permutation, the probability in (2) would be exactly m
for every U . In a -uniform permutation the probabilities are permitted to vary with U , but only by
an amount specied by the parameter . In our applications,  will be a xed polynomial function
of m; in this case we call  an almost uniform permutation.
The perhaps surprising result of this section is that, if the ratios of the weights are bounded,
it is possible to construct an almost uniform permutation that is guaranteed to be balanced. In
section 5.1 we will show how to dispense with any restrictions on the weights.
Theorem 3.3 Let fw
be any set of weights with jw for a constant B > 1. Then
there exists a balanced almost uniform permutation  on fw i g.
Assume rst that show how to
discharge this assumption later. Let I
Dene the means
Consider an arbitrary permutation  2 Sm . This induces permutations
We call  1 -good if, for every k 1 with 1
(M 1)
with an analogous denition for  2 . We call  -good if both  1
and  2 are -good. Thus in a good permutation, the partial sums of both positive and negative
weights are close to their expected values.
Now suppose  is chosen u.a.r. from Sm . A routine application of Hoeding's bound to the
partial sums (see Lemma A.1.1 in the Appendix) yields
Pr[ is not -good]  2m exp( 2 2
If we set
ln m, this probability is at most 2
Consider now a modied sample space in which  is selected u.a.r. among all
permutations. We shall write Pr unif for probabilities in the original uniform space to distinguish
them from those in this modied space. By the above calculation, for any event E  Sm we have
We are now in a position to construct our balanced almost uniform permutation. Let  be
chosen u.a.r. from all
m-good permutations, and let  1 ;  2 be the induced permutations on
To get a balanced permutation , we interleave  1 and  2 as follows. We take the rst
element from  1 , i.e., set Thereafter, for each k > 1 in turn we set (k) to be the
next element in  2 if
and the next element in  1 otherwise. Since
process is well-dened and yields a permutation  2 Sm . Moreover, since jw i j  M for all i it is
clear that  satises the balance condition (1).
We now need to verify the uniformity condition (2), for
arbitrary with jU j. Then we have
k1
4 Formally, we view 1 as a bijection from to I1 , and similarly for 2 . Throughout we shall adopt this
convention where appropriate, without comment.
where the second inequality follows from (5). Now some routine calculations involving Stirling's formula
(see Lemma A.1.2 in the Appendix) allow us to relate m 1
to m 1 +m 2
. Specically,
becomes
exp
m , and C > 0 is a universal constant. The quantity l measures the
deviation of the numbers k of positive and negative elements in U from the \expected" values
respectively. But since  is balanced,  is good, and the element sizes do not vary too
much, jlj cannot in fact be very large. To formalize this intuition, note rst that
since
. Now by the goodness condition (3) on  1 ;  2 we have
kg. Since  is balanced we also know that j
Together with (8) and our assumption that M  B, this implies the following bound on jlj:
Plugging in this value for jlj, the exponent in (7) is bounded above, for su-ciently large m, by
k(m
since k(m
2 and  1 ;  2  1. Thus (7) becomes
which veries the uniformity condition (2) with
This concludes the proof of the theorem for the special case
We can extend
the argument to general values of W using a simple trick. We will assume W > 0; the case W < 0
is entirely symmetrical. We begin by padding the sequence of weights with
wm+d each of which (except possibly the last) is M , so that
d  m. By the above argument for the case, we can construct a balanced almost uniform
permutation  0 on this padded sequence (though see the remark immediately following this proof).
Let  be the induced permutation on the weights fw i g n
. We claim that  is also balanced and
almost uniform.
To see that  is balanced, note that
for some k 0  k, using the balance property of  0 .
To see that  is almost uniform, let us call the indices true and the remainder fake.
Let U be an arbitrary subset of true indices of cardinality k. We need to show that
Since  is induced by  0 , this probability is bounded above by
is the event that  0 and the sum is over all S of the form U [ U 0 , where all
elements of U 0 are fake. Now by the almost uniformity of  0 , this sum is at most
d)
Pr unif [E S ]; (12)
where Pr unif denotes probability under the uniform distribution on permutations in Sm+d . But the
sum in (12) is just the expectation, under the uniform distribution, of the random variable
is the indicator r.v. of E S . Thus X counts the number of events E S that occur.
We claim that
This will complete the verication of condition (11); for replacing the sum in (12) by E(X) gives
which is of the required form since d  m.
To see the claim in (13), let E be the event that
so we have
Conditioning now on E , let r be the position in  0 of the last element of U , so that U
and  0 (r) 2 U . Also, let s be the position of the next true element, i.e.,  0 (s) is true and  0 (t) is
fake for r < t < s. (If no such element exists, let holds for precisely those
sets s. The number of such sets is just the number of fake elements
that fall between the true element at position r and the next true element (at position s), plus
one. The expectation of this quantity under the uniform distribution is plainly 1
m+1 . Plugging
this into (14) we get the value claimed in (13), which concludes the proof that  is almost uniform.
Remark: We should point out that the padded sequence we introduced in the second part of the
above proof might contain one weight whose absolute value is less than one. Thus it is not, in a
strict sense, a special case of the earlier case, where we assumed that all the weights had
absolute values in the range [1; B]. However, a more careful treatment of the analysis leading up
to equation (10) shows that this equation still holds even when there is a single small weight (or
even a constant number of small weights). Furthermore, we can make the constant C 0 that appears
in (10) independent of B.
following through the algebra in the second part of the proof, starting from equation (10),
and noting that d  m, it is not hard to check that the resulting permutation  is {uniform for
where the constant CB increases with B. Moreover,
it is also easy to verify that the permutation  actually satises a slightly stronger uniformity
property, namely

for any U with jU
1). (To get this value for C 0
that  must rst choose U and then l; this second choice introduces the
make use of these facts in section 5 when we discuss permutations of general weights.
4 A good
ow in the bounded ratios case
We now return to the random walk for the knapsack problem, and
esh out the sketch of a
ow
presented in the Introduction, making heavy use of the balanced almost uniform permutations from
section 3. We continue to consider only the bounded ratio case, i.e., we assume that all weights a i
lie in the range [1; B]. To avoid trivialities, we also assume B  b.
Let X;Y be two arbitrary vertices of
G
, viewed as subsets of ng. We need to specify
how to route one unit of
ow from X to Y . First, write are disjoint,
this can always be done since a i 2 [1; B]. Write similarly.
All the
ow leaving X will pass through X 1 , and all the
ow arriving at Y will pass through Y 1 .
Between X 1 and Y 1 , we will route the
ow using an almost uniform permutation. (Note that there
is an obvious correspondence between unit
ows from X 1 to Y 1 and probability distributions on
paths between them.) Let
be an arbitrary enumeration of the weights of the items in S, where weights in S \ Y 1
appear with a positive sign and weights in S \X 1 with a negative sign. Thus
We can now describe the
ow from X to Y in three stages:
Stage 1: Send the entire unit
ow along a single path from X to X 1 by removing the elements
of X 0 in index order.
Stage 2: Distribute the unit
ow along geodesic paths from X 1 to Y 1 according to a balanced
almost uniform permutation  of the weights fw i g of the items in S.
Stage 3: Send the entire unit
ow along a single path from Y 1 to Y by adding the elements of Y 0
in index order.
The role of stages 1 and 3 is simply to ensure that the endpoints of the random paths in stage 2 are
at least a small distance below the bounding hyperplane, to accommodate the (small)
uctuations
still present in balanced permutations.
Let us rst observe that the above
ow is valid. For this, we just need to check that all the
ow-carrying paths remain within the
set
. This is obvious for stages 1 and 3. For stage 2 it
follows from the balance property of : for if Z is the kth point along a
ow-carrying path from X 1
to Y 1 , then
b;
where in the last line we have used the fact that a(X 1 are both  b B. Hence Z.
Next we must bound the quantities C(f) and L(f) for this
ow f , as dened in section 2.
L(f ), the length of a longest
ow-carrying path, is plainly at most n + 2B. To estimate C(f ), we
must bound the
ow along any edge of
G
. For convenience we will in fact bound the
ow f(Z)
through any vertex Z; clearly this is also an upper bound on the
ow along any edge.
let Z be an arbitrary vertex of
G
. Dene P (Z) to be the set of pairs (X; Y ) such that
some
ow passes through Z. Note that P
are the pairs
whose paths pass through Z in stage i. We shall bound the contribution to f(Z) from each Pi (Z)
separately. For this is simple: since stage-1 paths have length at most B, the number of
vertices X such that (X; Y is (crudely) at most Bn B , so the contribution to f(Z) from
such paths is no more than Bn B
j. The same bound holds symmetrically for P3 (Z). The main
portion of the paths, P2 (Z), presents more of a challenge.
We shall actually work with e
P2 (Z), the set of pairs (X lies on the stage-2
path with endpoints . By the observation in the previous paragraph, the
ow contribution
from P2 (Z) will be at most B 2 n 2B times that from e
P2 (Z). Recall that we are really interested
in the ratio f(Z)
, rather than in f(Z) itself. Accordingly, following earlier analyses of this general
type (see, e.g., [9, 10]), we measure the set e
P2 (Z) by associating with each of its elements
an \encoding" Z 0 , which belongs
to
. This is dened as the complement of Z in the multiset
precisely,
To see that Z 0, we need to check that a(Z 0 )  b. But this follows because
b;
where in the second line we have used the balance property of  as in (16) to bound a(Z), this
time from below.
How many pairs (X could be mapped to a given Z 0 ? First note that Z 0 uniquely determines
both via the relations
Thus in particular such pairs share the same symmetric dierence, S, of cardinality m, say. To
determine X 1 and Y 1 uniquely, it su-ces to specify the subset U  S of elements that have already
been processed (i.e., added or deleted) by the stage-2 path by the time it reaches Z. For then we
know, from the fact that all stage-2 paths are geodesic, that X 1 agrees with Z on S U and with
Z 0 on U , and vice versa for Y 1 . More formally,
The upshot of the foregoing discussion is that we can dene a mapping from e
P2 (Z) to pairs of
the form (Z 0and U is a subset of Z Z 0 . Moreover, and crucially, this mapping
is injective. It therefore eectively enumerates the set e
P2 (Z).
Finally, we need to take account of the actual quantity of
ow traveling along the paths. Consider
a
P2 (Z), corresponding to the pair (Z Recall that the
ow distribution
between X 1 and Y 1 is determined by a balanced almost uniform permutation  of the weights
in . The proportion of this
ow that passes through Z is precisely
by the almost uniform property of .
Putting all this together, we can bound the total contribution to f(Z) from e
P2 (Z) as follows:
Z 0X
Z 0X
poly(n)
Z 0X
where in the summations j. The total contribution from all stage-2 paths is thus at
most
poly(n)j
j.
Combining this with our earlier bounds for stages 1 and 3, we obtain that f(Z)
poly(n)j
(for a dierent polynomial), and hence C(f)  poly(n). Since both L(f) and C(f) are bounded
polynomially in n, we now obtain immediately from Theorem 2.1 that the mixing time,  mix , is
polynomial in n. By keeping track of the polynomial factors, we see that the exponent is dominated
by the poly(n) term arising from the almost uniformity condition (2), which is of the form n O(B 2 )
(see the Remark at the end of section 3).
We summarize our analysis in the following theorem.
Theorem 4.1
Let
be the set of solutions to a knapsack problem whose weights a i lie in the range
[1; B] for some constant B. The mixing time of the random walk on
G
is
As mentioned in the Introduction, this immediately yields an fpras for computing
j in this case,
via a standard reduction to random sampling (whose details are spelled out in [11]).
5 The general case
We now generalize the results of the previous two sections to the case of arbitrary weights. The
essential ideas are the same, but there are several non-trivial technical complications that need to
be addressed.
5.1 Balanced almost uniform permutations
To handle arbitrary weights, we rst need to extend our construction of balanced almost uniform
permutations. The chief obstacle here is that it is no longer true (as in the bounded ratio case) that
each item of positive weight can be balanced by a bounded number of items of negative weight.
To overcome this di-culty, we will need to group items into \intervals" so that each interval has
approximately the same (positive or negative) weight. We can then reduce to the bounded ratio
case.
First we need a slightly more liberal balance condition:
Denition 5.1 Let fw
be a set of real weights, with
and let   1 be a nonnegative number. A permutation  2 Sm is -balanced if, for all k with
Our earlier denition (Denition 3.1) thus corresponds to  = 1.
Relaxing our earlier terminology slightly, we shall call  2 Sm a \balanced almost uniform
permutation" if  is -balanced for a xed constant , and -balanced for  a xed polynomial
function of m. The following theorem is a generalization of Theorem 3.3; it says that we can
construct a balanced almost uniform permutation for an arbitrary set of weights. Moreover, we can
bound the uniformity parameter  by a polynomial whose degree is arbitrarily close to 1=2 at the
cost of a modest increase in the balance parameter . This is almost the best that one can hope
for: it is easy to check that, if we have m=2 weights of +1 and m=2 of 1, then for any constants
, C and p < 1=2, there can be no -balanced Cm p -uniform permutation if m is su-ciently large.
For technical reasons, we shall actually prove a slightly stronger uniformity property. Call
strongly -uniform if
for every k with 1  k  m, every U  of cardinality k, and every l =
2 U . Note that the
expression on the right-hand side of (18) is just  times the probability of the given event if  were
chosen uniformly at random. Plainly (18) is a strengthening of equation (2) in Denition 3.2; recall
from equation (15) that our permutations in the previous section also had this stronger property.
Theorem 5.2 Fix 0 <  < 1 and let
90=. For any m and set of weights fw
exists a {balanced strongly Cm 1=2+ {uniform permutation, where C is a universal constant.
be a uniform random permutation in Sm . Let
1 be the smallest t such that the partial sum
w (i) has absolute value greater than b
(or
no such t exists). Similarly, let T 2 be the smallest t > T 1 such that j
M .
in the same way. Then let I 1 be the sequence f(i)g
, and I 2 the sequence
. Continue in this way, dividing  into intervals I
Now let  i be the aggregated weight of interval I i for
so the ratio of the weights of any two of these intervals is at
most ( b
. Thus, by the results of section 3, there exists a 1-balanced -uniform permutation
on f i g q 1
. By the Remark at the end of that section, we
can in fact assume that this permutation is strongly -uniform and (since ( b
is bounded
above by a constant, namely 1
p 1=10) that the constant C does not depend on . Call this
permutation  I . We claim that the permutation
I  I (1) I  I (2)    I  I (q 1) I q
obtained by rearranging the rst q 1 intervals according to  I is a -balanced Cm 1=2+ {uniform
permutation on the original m weights.
We prove the balance property rst. Let W
I is 1-balanced,
for all 1  j  q. Hence we have, for all j,
since the partial sums within any interval lie in the range [ b
Finally, note that jW
M . It follows that for all j,
and hence  is -balanced.
To verify the strong uniformity property, consider rst an alternative experiment in which the
permutation  I is chosen u.a.r. from S q 1 without regard to the balance property. Note that,
conditional on the value of q, the distribution of re-arranging
the intervals according to a uniform  I is a measure-preserving transformation, so  itself has the
uniform distribution. Thus we need to show that for any U and any index l =
U , the likelihood
ratio
Pr unif
where we write Pr unif for the probability when  I is uniform and Pr for the probability when
I is Cm 1=2+ {uniform. In fact, it su-ces to show that the above bound on the likelihood ratio
holds conditional on any . So x a permutation . In order for the numerator to be non-zero,
only the interval containing l can contain elements from both U and U c (the complement of U ).
Additionally, in the interval containing l, all the elements before l must be in U and all those
after l must be in U c . Let A 1 be the collection of intervals in fI i g q 1
containing only elements
of U , and A 2 the collection of intervals containing only elements of U c . Then jA must have
value either q 1 or q 2. Writing E 1 for the event  I for the event
I fq the above likelihood ratio is
Pr unif [E 1 and
In the case where jA 1 j+jA this is just the Cq 1=2+ {uniformity property; when jA 1 j+jA
it is the strong Cq 1=2+ {uniformity property. Thus  is strongly Cm 1=2+ {uniform, and the
proof is complete.
5.2 The
ow
Now that we have balanced almost uniform permutations for general weights, we can follow a
similar strategy to that in section 4 for constructing a good
ow in the general case. Our goal will
be to obtain a
ow f of cost we assume from now on that  is
arbitrary but xed.
Let X;Y be arbitrary vertices of
G
. Recall the scheme for constructing a
ow from X to Y in
the bounded ratio case in section 4: we essentially followed a balanced almost uniform permutation
of X  Y , except that we removed a constant number of items from X and Y from consideration
(processing them at the beginning and end of the path) to ensure that the path remained within
G
.
The idea in the general case is basically the same, except that we will now remove a xed number
of items from X [ Y and add/delete these repeatedly along the path to maintain ne balance.
Moreover, before applying the random permutation, we rst need to \pre-process" the pair (X; Y )
so that neither X nor Y is too close to the hyperplane: in contrast to the bounded ratio case, this
is not guaranteed by the removal of a xed number of items because of the possibly large variations
in weights. However, we can overcome this obstacle by randomly switching items between X and Y
to roughly balance their weights. The resulting
ow-carrying paths will not in general be geodesics,
as before, though they will have length only O(n).
In preparation for describing the
ow, we rst describe the pre-processing operation. We assume
that is the constant appearing
in Theorem 5.2. (In our application, we will reduce to this case by deleting a xed number of items
from X [ Y .) Call a pair of vertices
Our goal is to shift items randomly between X and Y and thereby reach a pair (X that is not
full.
Consider the following random walk on f(X
bg. If the current state is (X choose an index
probability 1, do nothing; else move i from X 0 to Y 0 or Y 0 to X 0 if possible. We call this the
\pre-processing random walk" (PRW). We claim in the following lemma that, if we run the PRW
for a number of steps chosen randomly between 1 and O(n), we will with reasonable probability
arrive at a pair (X that is not full. The proof uses a martingale argument and is deferred to
the

Appendix

.
Lemma 5.3 Let (X; Y ) be a full pair of vertices in
G
with
u.a.r. from f1;
constant (which depends only on ), and let (X be the result of running the PRW for T
steps starting from (X; Y ). Then Pr[(X positive constant C 2 (again
depending only on ).
We are now ready to construct and analyze the
ow in the general case.
Lemma 5.4 For arbitrary weights and any  > 0, it is possible to construct a multicommodity
ow f in
G
with
Proof: Let X;Y be arbitrary vertices of
G
. Viewing X and Y as subsets of
the elements of XY having largest weight (or let ties
broken according to index order. Dene
and let fw
be an arbitrary enumeration of the weights of the items in S, with the weights of
items in X appearing with negative and positive signs respectively. Let
We will say that a set of indices Z is good if Z Hand (Z X  Y ) H. For a set
of indices Z and an index i, dene
Z  fig if Z  fig is good;
Z otherwise.
on. Note that if l then the sequence
a path from X to Y in the unit hypercube of length at most l. This path need not in general lie
within
G
however, it is \close to"
G
in the sense that for every point Z of the path, Z H.
full then set choose T u.a.r. from
the constant in Lemma 5.3. Next, let
and Y is the result of running the PRW for T steps
starting from (X . So, by Lemma 5.3, we
can condition on the event that the pair (X 00 ; Y 00 ) is not full and thus increase the probability of
any path by a factor of at most C 2 .
Now let  be a -balanced, strongly Cm 1=2+ {uniform permutation on the weights fw i g, whose
existence is guaranteed by Theorem 5.2. We claim that the sequence
denes a path from X to Y in the hypercube. This is true because the condition that (X 00
not full, together with the fact that  is balanced, guarantees that all of the transitions indicated
by  will actually take place.
and let l = 2T +m. Then l is the sequence in (19). Our
ow from X to Y will essentially
follow the sequence j k , except that along the way elements of H will be used to keep the knapsack
as full as possible, but will be removed as necessary to make room for new items j k to be added.
Thus each intermediate state Z will be of the form H Xj 1    j k , for some H  H and k  l.
Suppose that, after processing the rst k  l elements of the sequence in (19), we have
The transition rule will be as follows.
1. If k < l and j
then move to Z j k+1 if possible (i.e., if the result is an element
of
otherwise delete an element from H.
2. If k < l and j k+1 2 Z then add an element from H if possible; otherwise move to Z j k+1 .
3. If l then add an element from H \Y if possible; otherwise delete an element from H \X.
The fact that all of the sets are good ensures that su-cient elements of H can
always be removed so as to make room to add the next element j k+1 when necessary; hence the
above rule denes a feasible random path from X to Y . Similarly, goodness also implies that
for every intermediate state Z; since our rule keeps the weight as large as
possible this implies that, at any intermediate edge (Z; W ) along the path, there exists (at most)
one element u 2 H such that
where z is the index such that exactly as in the
analysis in section 4, we dene the \encoding" Z 0 by
Thus, for any given edge (Z; W ), the number of encodings Z 0 is at most
j.
Note that the path from X to Y can be naturally divided into three stages, corresponding to
the three parts of the sequence j k . We will write the
ow through any given edge
G
as
is the contribution of stage i paths.
We will bound f by bounding each of the three contributions f i separately.
Consider stage 1 rst, and focus on a particular edge (Z; W ). For any pair (X; Y ) that sends
ow through (Z; W ) in stage 1, we can write are the rst k
elements processed along the path. Thus the pair (X; Y ) is completely specied by k;
and H, via the easily veried relations
The amount of
ow corresponding to a given sequence is bounded above by the probability
that were the rst chosen in the pre-processing random walk, which is
at most C 2 m (k+1) . (The factor C 2 here arises from our earlier conditioning on the event that
not full.) Thus we can bound the stage-1
ow f 1 (Z; W ) as in section 4. We have
where the factors C 1 m and 2 h arise from summing over k and H respectively.
The
ow f 3 (Z; W ) from stage-3 paths can be handled symmetrically, so consider now the stage-2
paths. For a given edge (Z; W ), every pair (X; Y ) that sends
ow through (Z; W ) in stage 2 can
be completely specied by Z is the number of elements of the
sequence in (19) processed along the path from X to Z and
. The amount of
ow corresponding to a given and U is bounded above by

where the rst factor comes from the pre-processing random walk, the second factor is the probability
of choosing a particular T , and the third factor is an upper bound on the probability
which comes from the strong almost uniformity of . Thus
we can again bound the
ow f 2 (Z; W ) as in section 4. We have
U




where the factors in the second line are written in the same order as the sums they arise from.
Adding the contributions f 1 , f 2 and f 3 , we see that the above
ow satises
while plainly was arbitrary, this completes the proof.
Given such a
ow, we need only invoke Theorem 2.1 to derive our main result.
Theorem 5.5
Let
be the set of solutions to an arbitrary instance of the 0-1 knapsack problem.
The mixing time of the random walk on
G
is
This immediately implies the existence of an fpras for computing
j in the general case.
Remark: The mixing time bound of O(n 9=2+ ) in Theorem 5.5 is reasonably tight for this type
of analysis. If we apply Theorem 2.1 to analyze random walk on the entire cube f0; 1g n , we get a
bound of O(n 3 ) even with an optimal
ow. Thus the truncation introduces an extra factor of only
O(n 3=2+ ) into the bound. It is instructive to see where this extra factor comes from: O(n 1=2+ ) is
due to the balanced almost uniform permutation construction (Theorem 5.2, which is tight), while
O(n) comes from the fact that the \encoding" Z 0 may lie just
outside
.
6 Multiple hyperplanes
6.1

Introduction

In this section, we will extend our earlier results to handle multiple hyperplanes. For a non-negative
real d  n matrix A and a positive real vector
let
denote the set of 0-1 vectors
for which Ax  b. The vertices
in
constitute the set of feasible solutions to the
multidimensional knapsack problem with the d simultaneous constraints
a j  x
a j
where a j
i  a ji . (In equation (21) the superscript j indexes the jth linear constraint; we will follow
this convention throughout.)
Geometrically,
is obtained by truncating the unit cube by d hyperplanes, each of which corresponds
to a knapsack constraint. The essential geometric property of these \knapsack" hyperplanes
is that their normal vectors all lie in the same quadrant. The results of this section will easily extend
to any collection of hyperplanes with this property 5 .
5 However, we cannot allow the hyperplanes to be arbitrary. If arbitrary truncations were allowed, then it would
be possible to use just two hyperplanes to cause exponential bottlenecks or even disconnect the graph
G
Following our earlier notation, we identify a 0-1 vector
with the set of indices
for the (now d-dimensional) weight of X.
As before we denote by
G
the subgraph of the hypercube f0; 1g n induced by the vertices in
and
we again study symmetric random walk on
G
i.e., transitions from a given state X  ng
are made as follows:
1. pick an item i ng u.a.r.;
2. if i 2 X, move to X fig; if
move to X [ fig; otherwise,
do nothing.
Again, to avoid issues involving periodicity, we add to every state a holding probability of 1
.
In this section we will prove that this random walk on
G
has mixing time that is polynomially
bounded in n, for any xed dimension d. Just as in the one-dimensional case, this immediately
gives a polynomial time algorithm for sampling (almost) uniformly at random
from
, and a fpras
for computing
j.
We note that the degree of our polynomial upper bound for the mixing time will depend on
the dimension d, but this is unavoidable as the following simple example shows. Consider a d-dimensional
knapsack problem in which there are n
2d items having each of the d weight vectors
n), and the remaining n
items have weight vector
the knapsack capacity is n). Let S be the set of feasible solutions
in
which do not
contain any of the items. Then
2d
d , but S is connected
to
only through
the origin. It follows easily that the mixing time is n
d) .
In fact, for arbitrary d there can be no uniform polynomial upper bound for the running time
of any sampling algorithm unless immediately by reduction from the
problem of sampling independent sets in a graph. By theorem 1.17 of [17], there is no algorithm
for (almost) uniformly sampling independent sets in a graph unless E)
is an arbitrary (undirected) graph, there is a 1-1 correspondence between the independent sets in
G and the feasible solutions to the knapsack problem with jV j variables and the jEj constraints
To prove rapid mixing of the random walk on
G
for any xed d, we use the multicommodity
ow technique as before. Recall that Theorem 2.1, which bounds the mixing time in terms of the
cost of a
ow f , holds for symmetric random walk on any connected subset of the hypercube, so it
again su-ces to come up with a
ow of small cost. As before, the idea is to spread each
ow evenly using a balanced almost uniform permutation. However, since the weight function a(  )
is now vector-valued, we rst need to extend the denition of balance to higher dimensions.
Denition 6.1 Fix an integer d > 0, and let fw
be a set of weights in R d satisfying
For a positive real number , a permutation  2 Sm is -balanced if
Thus  is balanced with respect to vector weights fw i g if and only if it satises the d one-dimensional
balance conditions given by (22). Note that this generalizes our earlier Denition 5.1 for the one-dimensional
case (except that, for simplicity, we have assumed that
Constructing balanced almost uniform permutations is signicantly more di-cult in higher
dimensions since one has to control
uctuations in all dimensions simultaneously. In fact, for
d  2, it is non-trivial to prove for an arbitrary set of vector weights that even a single balanced
permutation exists. (For of course this is trivial.) The existence of such a permutation follows
at once from a lemma due to Grinberg and Sevast'yanov [6], which was proved in an entirely dierent
context:
Lemma 6.2 [6] Let x be vectors in R d such that
there exists a permutation
where conv denotes the convex hull.
Of course, we need something much stronger than this, namely almost uniform permutations
with a similar balance property. Perhaps surprisingly, we will show that balanced almost uniform
permutations exist in arbitrary dimension d. To illustrate the main ideas involved in extending
from one to higher dimensions, we now give a sketch of the proof in the special case where
and the weights satisfy 1  jw j
In this setting, let I
. For every
be the projection of w i onto v ? . Let  1 be an almost uniform permutation on I 1
which is balanced (in the one-dimensional sense) with respect to fy i g i2I 1
, with a similar denition
for  2 . Finally, interleave  1 and  2 to give a permutation on which is balanced with
respect to fw 2
(the projections of the w i onto the second coordinate axis). Since  1 and  2 are
both almost uniform, so is , by an argument similar to that in the proof of Theorem 3.3.
Furthermore, since  1 and  2 are each balanced with respect to projections onto v ? , so is .
(Note that the projections y i satisfy
Thus, for every k, the projections
of
onto the second coordinate axis and onto v ? are both bounded, and since the w j
are
all in [1; 2], the angle between the coordinate axis and v ? is bounded away from zero. Thus, the
partial sums
stay inside a parallelogram of bounded diameter. Hence  is balanced with
respect to the weights fw
.
This concludes the sketch proof for the above special case with 2. Note that it is a
straightforward reduction to the one-dimensional result. Unfortunately, in general the reduction
from d to d 1 dimensions is not quite so straightforward; we deal with the extra technical di-culties
in the next subsection.
6.2 Balanced almost uniform permutations in arbitrary dimensions
The following theorem says that one can always construct balanced almost uniform permutations
when the dimension d is xed.
Theorem 6.3 Let d be any positive integer. There is a constant c d and a polynomial function
d such that, for any set of weights fw
in R d with
there exists a c d {balanced,
Proof: The proof will be by induction on d. The base case follows from Theorem 5.2,
with be arbitrary, and suppose that the result holds
for dimensions up to d 1. Let fw
be a set of weights in R d . Suppose rst that the weights
1jd
Thus each weight is at least half as large as the maximum (positive or negative) weight in some
coordinate. Then
1jd
d
W.l.o.g., suppose that the sum in the LHS is maximized by d. Then we have
(w d
(w d
j. Dene the means
. Note that  1
2d . For 1  j < d, let
For all
4, and
s be a p d 1 (m){uniform permutation on I s which is c d 1 {balanced with
respect to fy i g i2Is . Call  1 -good if for every k 1 with 1  k 1  m 1 we have
2
g. In similar fashion to the proof of Lemma A.1.1, Hoeding's bounds [7]
imply that for a particular value of k 1 we have
Pr unif ( 1 does not satisfy (25))  2 exp( 2 2 );
and since the event depends only on the initial segment  1
does not satisfy (25))  p d 1 (m)  Pr unif ( 1 does not satisfy (25))
Hence
Pr[ 1 is not -good]  mp d 1 (m)  2 exp( 2 2
Suppose that for some constants C and r, the polynomial p d 1 satises p d (k)  Ck r for all k. If we
then the RHS of (26) is at most 2Cm r+1 2(r+1)  1, for su-ciently large
m. Thus, we can assume that  1 is -good with probability 1 and only increase C by a constant
factor. Similar arguments apply to  2 .
Finally, note that it is always possible to interleave  1 and  2 to give a permutation on
which is 1-balanced with respect to fw d
. Let  be such a permutation. Then
we have j
ik
ik
ik
ik
ik
ik
for all j < d and k. Hence  is c 0
d {balanced for c 0
assumption (23) .
To verify almost uniformity, we follow the proof of Theorem 3.3. Let U
arbitrary with jU j. Then we have
k1
m2
Now we can bound the quantity m 1
by mimicking (with minor modications) the calculations
from equation (7) to equation (10) in the proof of Theorem 3.3. In our current setting, we have
2d
, and the jw d
are in [0; 2]. Because we have changed the denition of -good and
the value of , we also have to make the substitutions (B
respectively. Thus the bound on the exponent given in equation
Hence  is p d (m)-uniform for p d
We have shown how to make balanced almost uniform permutations if the weights satisfy
(23) and (24). To generalize to arbitrary weights fw
, we use the interval trick introduced in
section 5.1. Let  be a uniform random permutation in Sm , and let T
similarly. Now use the T i to divide  into intervals I
be the aggregated (d-dimensional) weights of the rst q 1 intervals. Note that if we
divide each  j
then the resulting weights satisfy (23) and (24). Hence these weights
admit a c 0
d {balanced, p d (q){uniform permution (though see the remark immediately following this
proof). Rearranging the intervals fI i g q 1
according to such a permutation gives a permutation on
which is p d (m){uniform and c d {balanced for c
Remark: We should point out that the weights f i g q 1
of the rst q 1 intervals will not in
general sum to zero. However, we can easily get around this by introducing a dummy weight  q
which is equal to the weight of interval I q . The presence of this single small weight does not aect
equation (27) for su-ciently large m. Hence there is a c 0
d -balanced p d -uniform permutation on this
padded sequence f i g q
. This induces a permutation on f i g q 1
which is (c 0
1){balanced and
cp d (q){uniform for some constant c. Thus, if we incorporate an extra +1 into the constant c 0
d and
an extra factor of c into p d then the argument in the above proof is still valid.
Before we specify our
ow, we need one more denition.
Denition 6.4 Let fw
be a sequence in R d , with w
l be a positive integer. A permutation  is strongly l{balanced if, for all k  m
and j  d, there exists a set S  l, such that
and
have opposite signs (or either is 0).
Thus, in a strongly balanced permutation, whenever the initial segment f(i)g k
is \above average"
with respect to a particular coordinate j, it can be made \below average" by
ipping at most some
xed number l of items, and vice versa. As the name suggests, the strong balance condition is
stricter than the usual balance condition. Nonetheless, the following lemma says that strongly
balanced permutations always exist.
Lemma 6.5 For any sequence fw
in R d , there exists a strongly 16d 2 {balanced permutation.
Note that this lemma claims only that a single strongly balanced permutation exists; unlike Theorem
6.3, it makes no claims regarding almost uniformity. The proof of the lemma relies heavily on
the result of Grinberg and Sevast'yanov quoted earlier (Lemma 6.2); the proof is straightforward
but rather technical, so we defer it to the Appendix.
6.3 A good
ow
Now that we have multi-dimensional balanced almost uniform permutations and strongly balanced
permutations, we are ready to contruct a good
ow.
Lemma 6.6 Fix any number of knapsack constraints d. For arbitrary item weights, it is possible to
construct a multicommodity
ow f in
G
with C(f) bounded by a polynomial in n and
Proof: Recall that we identify each vertex xwith the index set
d is the constant in the construction of
balanced almost uniform permutations as in Theorem 6.3. Our main goal will be to construct a
ow b
f which, simultaneously for every X;Y 2 b
sends one unit of
ow from X to Y . This
ow
will satisfy C( b
f)  poly(n) and L( b
Note that, from any vertex X 2
we can obtain a vertex b
by removing at most 3dc d
items. Thus, we can use an approach similar to that in section 4 to extend b
f to a multicommodity
ow f on the whole of
and f will satisfy C(f)  n 6dc d poly(n)  poly 0 (n) and L(f)  L( b
It remains to dene the
ow b
f and show that it has the properties claimed. Fix X;Y 2 b
As usual, the path from X to Y will follow a permutation  on the symmetric dierence X  Y .
However, as in the one-dimensional case, a simple balanced almost uniform permutation  will
not do; such a permutation would not necessarily dene a path that stayed in
The problem
occurs when for some j, max i2X a j
i is not comparable to max i2Y a j
. (For example, if max i2X a j
then the path could have too much variation in the j{direction as it approached Y .)
However, we can deal with this problem by considering the \large" and the \small" items in XY
separately.
g. Let
are the \large" and \small" items respectively.)
Let fw i g i2XY be an enumeration of the weights of the items in X  Y , where weights from Y
appear with a positive sign and weights from X appear with a negative sign. Let
and let
i2S w i . Let  1 be a permutation on L which is strongly 16d 2 {balanced with
respect to the weights fw i g i2L , and let  2 be a p d (jSj){uniform permutation which is c d {balanced
with respect to the weights fw i  2 g i2S . The existence of  1 and  2 is guaranteed by Lemma 6.5
and Theorem 6.3 respectively. To obtain , we will interleave the strongly balanced permutation
1 and the balanced permutation  2 . The rule for interleaving will be as follows. Suppose that
have already been assigned, and that g.
or k2
, so we can dene
Now let
. We claim that  satises the following condition.
Fix j and k. Then there exist sets of indices V 1 and V 2 , with jV i
We will prove this in the case  1
j the proof is similar. Again, let k
so that g.
The method of interleaving ensures that
Therefore, since  1
j , we have
Clearly, the strong balance condition on  1 implies that there exist A; A 0 , with jA
similarly for A 0 , such that
Also, by the balance condition on  2 we have
g). Then we have
Exactly analogous relations hold with B; A replaced by B . Combining this with equations
(30){(35) gives (28) and (29).
determines a path fZ i g jXY j
i=0 from X to Y , where Z
for 1  i  jX  Y j. This path might not stay in
but we can alter it slightly so that it
does. Equations (28) and (29) imply that for every k and j, there exists a set of indices W j
k with
a
a
k . Then, for all k, jW k j  34d 3 , and
Then each Z k 2
Our
ow from X to Y will pass through each of the Z k in turn. To get from Z k
to Z k+1 , we perform the following steps:
1. Remove each item in Z k (Z k \ Z k+1 ) in index order.
2. Add each item in Z k+1 (Z k \ Z k+1 ) in index order.
By analogy with sections 4 and 5,
for each intermediate point Z along the path dene the \encoding" Z 0 by
and let kg. In similar fashion to our earlier analysis one can see that, for a given Z,
and Y are completely specied by the 4-tuple (Z
a
a
a
where the second inequality follows from (37). Hence Z 0 2
We can therefore bound the
ow
f(Z) through Z by
Z 0X
Wx;Wy;U
Finally, for a given X and Y , let
g, so that
. Note that
for every j, L j \ Y is equal to either L j or ;. Thus, if we dene k
of M and k 2 , there are at most 2 d jSj
possible values for U in the inner sum of equation (38).
Therefore, we have
Z 0X
M;Wx;Wy ;k 2
Z 0X
M;Wx;Wy ;k 2

Z 0X
M;Wx;Wy ;k 2
Z 0n d
poly(n)j
where in the second line we have appealed to the almost uniformity of permutation  2 . This
completes the proof.
Given such a
ow, we can appeal to Theorem 2.1 to derive the main result of this section.
Theorem 6.7 Fix any dimension d > 0, and
let
be the set of solutions to an arbitrary instance
of the d-dimensional 0-1 knapsack problem. The mixing time of the random walk on
G
is poly d (n).
As in one dimension, this immediately implies the existence of an fpras for computing
j in this
more general setting.

Acknowledgments

We thank Persi Diaconis for bringing reference [6] to our attention.



--R

Polytopes, permanents and graphs with large factors.
Comparison techniques for reversible Markov chains.
Geometric bounds for eigenvalues of Markov chains.
A mildly exponential time algorithm for approximating the number of solutions to a multidimensional knapsack problem.

Value of the Steinitz constant.
Probability inequalities for sums of bounded random variables.
Mathematical foundations of the Markov chain Monte Carlo method.
Approximating the permanent.

The Markov chain Monte Carlo method: an approach to approximate counting and integration.
Random generation of combinatorial structures from a uniform distribution.
Markov chains and polynomial time algorithms.
Random walks in convex sets.
Lectures on
Improved bounds for mixing rates of Markov chains and multicommodity ow.
Randomised algorithms for counting and generating combinatorial structures.
--TR
random permutations;knapsack problem;balanced permutations;random sampling;hypercubes;markov chains;random walks