About the Structure of the Integer Cone and
its Application to Bin Packing∗
Klaus Jansen1 and Kim-Manuel Klein1

arXiv:1604.07286v2 [] 8 Dec 2016

1

Department of Computer Science, University of Kiel,
{kj,kmk}@informatik.uni-kiel.de

We consider the bin packing problem with d different item sizes and revisit the
structure theorem given by Goemans and Rothvoß [GR14] about solutions of the
integer cone. We present new techniques on how solutions can be modified and give
a new structure theorem that relies on the set of vertices of the underlying integer
polytope. As a result of our new structure theorem, we obtain an algorithm for the
O(d)
· enc(I)O(1) , where V is the set of
bin packing problem with running time |V |2
vertices of the integer knapsack polytope and enc(I) is the encoding length of the
bin packing instance. The algorithm is fixed parameter tractable, parameterized by
the number of vertices of the integer knapsack polytope |V |. This shows that the
bin packing problem can be solved efficiently when the underlying integer knapsack
polytope has an easy structure, i.e. has a small number of vertices.
Furthermore, we show that the presented bounds of the structure theorem are
asymptotically tight. We give a construction of bin packing instances using new
structural insights and classical number theoretical theorems which yield the desired
lower bound.

1 Introduction
Given the polytope P = {x ∈ Rd | Ax ≤ c} for some matrix A ∈ Zm×d and a vector c ∈ Zd . We
consider the integer cone
int.cone(P ∩ Zd ) = {

X

d

P∩Z
λp p | λ ∈ Z≥0
}

p∈P∩Zd

of integral points inside the polytope P. Let PI = Conv(P ∩Zd ) be the convex hull of all integer
points inside P, where for given set X ⊂ Rd , the convex hull of X is defined by Conv(X) =
P
{ p∈X xp p | x ∈ [0, 1]X , kxk1 = 1}. Let VI be the vertices of the integer polytope PI i.e.
P
P∩Zd },
PI = Conv(VI ). In case of the (fractional) cone Cone(P ∩ Zd ) = { p∈P∩Zd λp p | λ ∈ R≥0
we know by Caratheodory’s Theorem (see e.g. [Sch86]) that each γ ∈ PI can be written as a
convex combination of at most d + 1 points in VI and hence Cone(P ∩ Zd ) = Cone(VI ).
In this paper we investigate the structure of the integer cone int.cone(P∩Zd ) versus int.cone(VI ).
Therefore, we define the vertex distance of a point b ∈ int.cone(P ∩ Zd ) which describes how
∗

This work was partially supported by DFG Project, Entwicklung und Analyse von effizienten polynomiellen
Approximationsschemata für Scheduling- und verwandte Optimierungsprobleme, Ja 612/14-2

1

many extra points from (P ∩ Zd ) \ VI are needed to represent b. The vertex distance is defined
by
d

P∩Z
I
Dist(b) = min{kγk1 | γ ∈ Z≥0
, λ ∈ ZV≥0
such that b =

X

v∈VI

λv v +

X

γp p}

p∈PI

In this paper we show that for every point b ∈ int.cone(P ∩ Zd ), the vertex distance Dist(b) is
P
P
O(d)
. Hence, every b can be written by b = v∈VI λv v + p∈P∩Zd γp p for some
bounded by 22

P∩Z , where kγk ≤ 22
I
.
λ ∈ ZV≥0
and some γ ∈ Z≥0
1
A related result concerning the structure of the integer cone was given by Eisenbrand and
Shmonin [ES06]. They proved that every b ∈ int.cone(P ∩ Zd ) can be written by a vector
P∩Zd with b = P
λ ∈ Z≥0
p∈P∩Zd λp p such that λ has a bounded support (=number of non-zero
components). Therefore, for a given set M and given vector λ ∈ RM
≥0 , let supp(λ) be the set of
non-zero components of λ, i.e. supp(λ) = {s ∈ M | xs 6= 0}.
d

O(d)

Theorem 1 (Eisenbrand, Shmonin [ES06]). Given polytope P ⊂ Rd . For any integral point
P∩Zd such that b = P
b ∈ int.cone(P ∩ Zd ), there exists an integral vector λ ∈ Z≥0
p∈P∩Zd λp p and
d
|supp(λ)| ≤ 2 .
Let (s, b) be an instance of the bin packing problem with item sizes s1 , . . . , sd ∈ (0, 1] and
multiplicities b ∈ Zd≥0 of the respective item sizes. The objective of the bin packing problem
is to pack all items b into as few unit sized bins as possible. When we choose P to be the
d
I
knapsack polytope, i.e. P = {x ∈ Zd≥0 | sT x ≤ 1}, then a vector λ ∈ ZP
≥0 of int.cone(P ∩ Z )
yields a packing for the bin packing problem. A long standing open question was, if the bin
packing problem can be solved in polynomial time when the number of different item sizes d
is constant. This problem was recently solved by Goemans and Rothvoß [GR14] using similar
structural properties of the integer cone. They proved the existence of a distinguished set
X ⊂ P of bounded size such that for every vector b ∈ int.cone(P ∩ Zd ) there exists an integral
P∩Zd where most of the weight lies in X. More precisely, they proved the following
vector λ ∈ Z≥0
structure theorem:
Theorem 2 (Goemans, Rothvoß [GR14]). Let P = {x ∈ Rd | Ax ≤ c} be a polytope with
A ∈ Zm×d , c ∈ Zd such that all coefficients are bounded by ∆ in absolute value. Then there
exists a set X ⊆ P ∩Zd with |X| ≤ md dO(d) (log ∆)d such that for any point b ∈ int.cone(P ∩Zd ),
P∩Zd such that b = P
there exists an integral vector λ ∈ Z≥0
p∈P∩Zd λp p and
1. λp ≤ 1

∀p ∈ (P ∩ Zd ) \ X

2. |supp(λ) ∩ X| ≤ 22d
3. |supp(λ) \ X| ≤ 22d
The set X is constructed in [GR14] by covering P by a set of integral parallelepipedes. The set
X consists of the vertices of the integral parallelepiped and can be computed in a preprocessing
step. Note that by the construction of Goemans and Rothvoß, we have that VI ⊂ X as the set
of vertices of some inner centrally symmetric polytopes is computed.

1.1 Our results:
At first, we study the special case when P is given by the convex hull of integral points
B0 , B1 , . . . , Bd ∈ Zd i.e. P is the simplex S = Conv(B0 , B1 , . . . , Bd ). This is for example
the case in the knapsack polytope when all items sizes are of the form si = 1/ai for some
ai ∈ Z≥1 . In this case, all vertices of the knapsack polytope are of the form B0 = (0, . . . , 0)T
and Bi = (0, . . . , 0, ai , 0, . . . , 0)T for 1 ≤ i ≤ d and therefore integral. We prove the following
theorem:

2

Theorem 3. Let S be the simplex defined by S = Conv(B0 , B1 , . . . , Bd ) for Bi ∈ Zd and let B
be the set of vertices B = {B0 , B1 , . . . , Bd }. For any vector b ∈ int.cone(S ∩ Zd ), there exists
S∩Zd with b = P
an integral vector λ ∈ Z≥0
s∈S∩Zd λs s and
O(d)

1. λs ≤ 22

∀s ∈ (S ∩ Zd ) \ B

2. |supp(λ) \ B| ≤ 2d
This theorem shows that in the case that the integer polytope PI is a simplex, the vertex
O(d)
for any b ∈ int.cone(P ∩ Zd ). In Section 3,
distance Dist(b) can be bounded by a term 22
we complement this result by giving a matching lower bound for Dist(b). We prove that the
double exponential bound for Dist(b) is tight, even in the special case of bin packing, where the
simplex S is a specific knapsack polytope. The lower bound is based on the sylvester sequence
Q
Si which is inductively defined by S1 = 2 and Si+1 = ( ij=1 Sj ) + 1 [GKP94].

Theorem 4. There exists a bin packing instance with sizes a11 , . . . , a1d for ai ∈ Z≥1 and multiplicities b ∈ Zd≥0 corresponding to a point b ∈ int.cone(P ∩Zd ), where P is the knapsack polytope
such that
Ω(d)

Dist(b) ≥ Sd − 2 = 22

Furthermore, in the end of Section 4, we discuss the difficulty of finding instances with large
vertex distance and we show a connection to the modified roundup property (see [ST97]).
As a direct consequence of our main Theorem 3, we obtain a structure theorem that is similar
to the one given by Goemans and Rothoß[GR14] but uses a different set X ⊂ P of distinguished
points. Instead of the set of vertices of integral parallelepipedes, our theorem uses the set of
vertices VI of the integer polytope.
Theorem 5. Let P = {x ∈ Rd | Ax ≤ c} be a polytope with A ∈ Zm×d , c ∈ Zd≥0 and let
VI ⊆ P ∩ Zd be the set of vertices of the integer polytope PI with Conv(VI ) ∩ Zd = P ∩ Zd .
P∩Zd such that
Then for any vector b ∈ int.cone(P ∩ Zd ), there exists an integral vector λ ∈ Z≥0
P
b = p∈P∩Zd λp p and
O(d)

1. λp ≤ 22

∀p ∈ (P ∩ Zd ) \ VI

2. |supp(λ) ∩ VI | ≤ d · 2d
3. |supp(λ) \ VI | ≤ 22d
This theorem finally shows that for arbitrary polytopes P and any b ∈ int.cone(P ∩ Zd ), the
O(d)
and hence independent of the number of inequalities
vertex distance Dist(b) is bounded by 22
m and the largest entry ∆ in the description of P.
Recall that a parameterized problem with parameter p and input I is called fixed parameter
tractable (fpt) if there exists an algorithm with running time O(f (p) · enc(I)O(1) ) for some
computable function f of p which is independent of I and enc(I) is the encoding length of
instance I. We refer to the book of Downey and Fellows [DF99] for more details on parameterized
complexity. As a consequence of our structure theorem, we present in Section 2 an algorithm for
O(d)
· log(∆)O(1) , where ∆ is the maximum
the bin packing problem with a running time of |VI |2
over all multiplicities b and denominators in s. Since |VI | ≥ d + 1 this is an fpt-algorithm
parameterized by the number of vertices of the integer knapsack polytope VI .
Theorem 6. The bin packing problem can be solved in fpt-time parameterized by the number
of vertices VI of the integer knapsack polytope.

3

This theorem shows that the bin packing problem can be solved efficiently when the underlying
knapsack polytope has an easy structure i.e. has not too many vertices. However, since the
total number of vertices is bounded by O(log ∆)d [HL83] the algorithm has a worst case running
O(d)
, which is identical to the running time of the algorithm by Goemans and
time of (log ∆)2
Rothvoß [GR14].

1.2 Related results
The bin packing problem is one of the most fundamental combinatorial problems in computer
science. It has been very well studied in the literature, mostly in the context of approximation. A major contribution was given by Karmarkar and Karp [KK82]. They presented a
polynomial time approximation algorithm with a guarantee of OP T + O(log2 (OP T )). Very
recently, this famous result by Karmarkar and Karp was improved by Rothvoß [Rot13] who
presented an algorithm with guarantee OP T + O(log OP T log log(OP T )) and later by Hoberg
and Rothvoß [HR15] who improved the guarantee further to OP T + O(log(OP T )). Concerning
the bin packing problem when the number of different item sizes d is constant, Jansen and
Solis-Oba [JS11] presented an approximation algorithm with a guarantee of OP T + 1. Their
O(d)
· enc(I)O(1) and therefore is fpt in the number of differalgorithm has a running time of 22
ent item sizes d. Finally, as mentioned above, Goemans and Rothvoß [GR14] presented their
O(d)
.
polynomial time algorithm for the bin packing problem with running time (log ∆)2
P∩Zd with
In a very recent work, Onn [Onn15] discussed the problem of finding a vector λ ∈ Z≥0
P
b = p∈P∩Zd λp p for given b ∈ int.cone(P ∩ Zd ). He presented an algorithm for the case that
the polytope P = {x ∈ Rd | Ax ≤ c} has a specific shape. In the case that the matrix A is
totally unimodular he gave a polynomial time algorithm even in the case that the dimension d
is variable.

2 Proof of the main theorem
Given simplex S = Conv(B0 , B1 , . . . , Bd ) for Bi ∈ Zd≥0 and a vector b ∈ int.cone(S ∩ Zd ). We
consider integral points in cone(B) generated by the vertices B = {B0 , B1 , . . . , Bd } = VI of the
simplex S. For convenience, we denote by B also the matrix with columns B0 , B1 , . . . , Bd . As
our main subject of investigation, we consider the parallelepiped
Π = {x0 B0 + x1 B1 + . . . + xd Bd | xi ∈ [0, 1]}.
By definition of S = {x0 B0 + x1 B1 + . . . + xd Bd | xi ∈ [0, 1], i xi = 1} we have that S ⊂ Π.
Furthermore, one can easily see that cone(B) can be partitioned into parallelepipedes Π (see
figure 1 with B0 = 0), as each point b = x0 B0 + x1 B1 + . . . + xd Bd ∈ cone(B) ∩ Zd for some
x ∈ Rd≥0 can be written as the sum of an integral part Bxint = ⌊x0 ⌋B0 + . . . + ⌊xd ⌋Bd and a
fractional part [Bx] = {x0 }B0 + . . . + {xd }Bd ∈ Π (we denote the fractional part of some v ∈ R
by {v} = v − ⌊v⌋ and for some vector x ∈ Rd we denote by {x} the vector ({x0 }, . . . , {xd })T .
For vector b ∈ Cone(B) with b = Bx let [b] = [Bx]. We say that two points b, b′ ∈ Cone(B) are
equivalent if [b] = [b′ ].
P∩Zd with b = P
For the proof of the main theorem, we consider a λ ∈ Z≥0
s∈S λs s and suppose
that λ does not fulfill property (1) of Theorem 3. Then there exists a γ ∈ (P ∩ Zd ) \ VI with big
Ω(d)
weight i.e. λγ ≥ 22 . The key idea of the proof is that we consider the set of multiplicities
γ, 2γ, 3γ, . . . of the vector γ. Our goal is to find a possibly small multiplicity K > 1 such that
Kγ is equivalent to a point δ in the convex hull S. Hence, weight on γ can be shifted to the
P
vertices B0 , . . . , Bd of S. Then Kγ can be written as the sum of vertices
Λi Bi plus some
δ ∈ S ∩ Zd (see Lemma 1 for a detailed proof). In figure 1 we have that 3γ is equivalent to a
point in the simplex (as remarked by the grey areas) and hence in that case 3γ = δB1 + B2 for
P

4

3γ
2γ

B1
γ

Π
B2

B0 = 0

Figure 1: Partitioning Cone(B)
some δ ∈ S. Before we are ready to prove the existence of a small multiplicity K, we give some
definitions and observations.
Instead of multiplicities of γ ∈ S ∩ Zd , we consider multiplicities of a vector x ∈ [0, 1)d+1 in
the unit cube with γ = x0 B0 + x1 B1 + . . . + xd Bd = Bx.
Definition 1. Consider multiplicities x, 2x, 3x, . . . of a vector x ∈ [0, 1)d+1 with
say components i jumps at K if ⌈Kxi ⌉ > ⌈(K − 1)xi ⌉. We define
Level(Kx) =

P

xi = 1. We

d
X

{Kxi }.

i=0

Note that Level(Kx) is always integral as Level(Kx) = di=0 Kxi − di=0 ⌊Kxi ⌋ and both
P
P
terms di=0 Kxi and di=0 ⌊Kxi ⌋ are integral. The following lemma shows that we obtain the
desired decomposition of Kγ if Level(Kx) = 1.
P

P

Lemma 1. Let γ ∈ S ∩ Zd be the vector with γ = Bx for x ∈ [0, 1)d+1 . If Level(Kx) = 1, then
d
there exists a Λ ∈ Zd+1
≥0 and a δ ∈ S ∩ Z such that
Kγ = δ +

d
X

Λi Bi .

i=0

int
Proof. As above, we split every component i of Kx ∈ Rd+1
≥0 into an integral part Kxi = ⌊Kxi ⌋
and a fractional part {Kxi }. Then Kx = Kxint + {Kx} and we set δ = B({Kx}) = [B(Kx)].

Observation 1. δ ∈ Zd .
Since Kγ = KBx ∈ Zd and KBxint ∈ Zd we obtain that δ = B({Kx}) = B(Kx) − B(Kxint )
is integral and therefore δ ∈ Zd .
Observation 2. δ ∈ S.
Since Level(Kx) = 1 we obtain that di=0 {Kxi } = 1 and δ = B({Kx}) = ({Kx0 })B0 + . . . +
({Kxd })Bd , we can state δ as a convex combination of B0 , B1 , . . . Bd . Therefore δ ∈ S.
Finally, we can decompose Kγ into
P

Kγ = KBx = B({Kxd }) + B(Kxint ) = B(Kxint ) + δ = δ +

d
X
i=0

for some Λ ∈ ZB
≥0 .

5

Λi Bi

The following lemma gives a correlation between the level of some point Kx and the number
of jumps.
Lemma 2. Let J be the number of jumps at K, then
Level(Kx) = Level((K − 1)x) + 1 − J.
Proof. For every component i of Kx which jumps, we obtain that {Kxi } = {(K − 1)xi + xi } =
{(K − 1)xi } + xi − 1. Hence
Level(Kx) =

d
X

{Kxi }

i=0

=

X

i jumps at K

=

d
X

X

({(K − 1)xi } + xi − 1) +

({(K − 1)xi } + xi )

i does not jump at K

{(K − 1)xi } +

i=0

d
X

xi − J = Level((K − 1)x) + 1 − J.

i=0

Pd

Theorem 7. Given x ∈ [0, 1)d+1 with Level(x) =
P
O(d)
such that Level(Kx) = di=0 {Kxi } = 1.
K ≤ 22

i=0 xi

= 1. Then there is a K ∈ N>1 with

Proof. We suppose that 12 > x0 ≥ x1 ≥ . . . ≥ xd . In the case that x0 ≥
Level(2x) ≤ 1 and are done. Let d¯ ≤ d be the smallest index such that
d
X

xi <

¯
i=d+1

1
2

we obtain that

1
x ,
¯ d¯
X(d)

¯ = Qd¯ pi and pi = ⌈ 1 ⌉. Intuitively, d¯ is chosen such that there is a major jump
where X(d)
i=0
xi
from xd¯ to xd+1
¯ , i.e. xd¯ >> xd+1
¯ . Note that the above equation is always fulfilled for d¯ = d
¯
and since X(1d)
¯ xd¯ < xd¯ < 1/2 we have that d ≥ 1. First, we prove the following lemma to give
¯ and x ¯
bounds for X(d)
d

P
Lemma 3. Assuming for every 0 ≤ j ≤ d¯ that di=j+1 xi ≥
ters can be bounded by
¯ ≤ 22O(d) and
• X(d)

• component xd¯ ≥

1
Ω(d)

22

1
X(j) xj ,

then the following parame-

.

1
Proof. For j = 0 we know that x0 ≥ d+1
as x0 is the largest component. This implies also that
¯
X(0) ≤ d + 1. We suppose by induction that for every j ≤ d,
2j

2j

xj ≥ (2j2 · d2 )−1
and
2j+1

2j+1

· d2

X(j) ≤ (2j2

).

1
xj and since the coefficients are sorted in nonSince j ≤ d¯ we obtain that i=j+1 xi ≥ X(j)
1
increasing order we get dxj+1 ≥ X(j) xj . Using the induction hypothesis this gives

Pd

2j+1

xj+1 ≥ (2j2

2j+1

d2

2j+1 +j22j

2j +22j+1 +1

≥ (2j2

2j+1

> (22·j2

2(j+1)

= (2j2

2j

2j

)−1 · (2j2 d2 )−1 · d−1

· d2

2j+1

· d2·2

2(j+1)

· d2

6

)−1

)−1

)−1

Product X(j + 1) can be bounded as follows:
X(j + 1) = ⌈

1
1
⌉X(j) ≤ (
+ 1)X(j)
xj+1
xj+1
2(j+1)

≤ (2(j+1)2

2(j+1)

d2

2(j+1) +1

< 2(j+1)2

2(j+1)

d2

2(j+1) +1+j22j+1

= 2(j+1)2

2(j+1)

< 22·(j+1)2

2j+1

+ 1) · 2j2
2j+1

· 2j2

2j+1

d2

2j+1

d2

2(j+1) +22j+1

· d2

2(j+1)

· d2·2

2(j+1)+1

= 2·(j+1)2

2(j+1)+1

· d2

¯
¯
2d¯
O(d)
2d+1
¯ 2d¯
¯ 2d+1
¯ ≤ (2d2
and xd¯ ≥ (2d2 ·d2 )−1 =
) = 22
·d2
As a result we obtain that X(d)

1
Ω(d)

22

.

¯ for each component 0 ≤ i ≤ d, we define the distance Di (K) of a multiplicity
Let X = X(d),
K by Di (K) = j, where j ≥ 0 is the smallest integer such that component i jumps at K + j.
Note that Di (K) is bounded by pi as pi xi ≥ 1. We say Kx ≡ K ′ x if for every 0 ≤ i ≤ d¯
the distance Di (K) = Di (K ′ ). Consider elements x, 2x, . . . , (X + 1)x. Since the number of
Q¯
equivalence classes is bounded by X = di=1 pi , there exist two elements Kx, (K + Z)x with
K, Z ∈ Z≥1 and K, (K +Z) ≤ X +1 such that Kx ≡ (K +Z)x. We will see that the equivalence
of two multiplicities implies the existence of a multiplicity M > 1 with Level(M x) = 1.
P
First, we argue about the level of multiplicity Z −1. Note that since di=0 xi = 1 we have that
Pd
¯
Level(Kx) = i=0 {Kxi } for every multiplicity K ∈ Z≥1 . The case that Level((Z −1)x) ≥ d+2
is not possible since
Level((Z − 1)x) =

d
X

{(Z − 1)xi } ≤ d¯ + 1 + (Z − 1)

d
X

xi ≤ d¯ + 1 + (X − 1)

¯
i=d+1

i=0

d
X

xi

¯
i=d+1

≤ d¯ + 1 +

X −1
xd¯ < d¯ + 2.
X

Case (1). Suppose Level((Z − 1)x) = d¯ + 1 (for Z ≥ 2).
¯
Case (1a). Suppose {(Z − 1)xi } ≥ 1 − xi for all i = 0, 1, . . . , d.
In this case every component 0 ≤ i ≤ d¯ jumps at Z. By Lemma 2, we can bound the level of
Zx by Level(Zx) ≤ Level((Z − 1)x) + 1 − (d¯ + 1) = 1.
Case (1b). There is an 0 ≤ i ≤ d¯ such that {(Z − 1)xi } < 1 − xi .
In this case

Pd¯

i=0 {(Z

Level((Z − 1)x) =

d
X

− 1)xi } ≤ d¯ + 1 − xi ≤ d¯ + 1 − xd¯ and we obtain

{(Z − 1)xi } < d¯ + 1 − xd¯ +

d
X

1
(Z − 1)xi ≤ d¯ + 1 − xd¯ + xd¯ < d¯ + 1
X

¯
i=d+1

i=0

which contradicts the assumption of Case 1.
¯
Case (2). Suppose Level((Z − 1)x) ≤ d.
Since K ≡ K +Z we know that every component i jumps at K +Di and K +Z +Di , hence for
every 0 ≤ i ≤ d¯ we obtain {(K +Di )xi } < xi and {(K +Z +Di )xi } < xi . Let {(K +Di )xi } = α1
and {(K + Z + Di )xi } = α2 for some α1 , α2 < xi . Then {Zxi } = {α2 − α1 } and hence {Zxi } =
α2 − α1 if α1 ≤ α2 and {Zxi } = 1 + α2 − α1 if α1 > α2 . Since α1 , α2 < xi we have {Zxi } < xi
or {Zxi } ≥ 1 − xi . Hence every component 0 ≤ i ≤ d¯ jumps at Zxi or at (Z + 1)xi . We obtain
by Lemma 2 that Level((Z + 1)x) ≤ Level((Z − 1)x) + 2 − (d¯ + 1) ≤ d¯ + 2 − (d¯ + 1) = 1.

7

Proof of the main Theorem 3
d

Consider the vector b ∈ int.cone(S ∩ Zd ). Let λ ∈ ZS∩Z be the integral vector with b =
P
s∈S∩Zd λs s.
Ω(d)
Assume there is a component γ ∈ (S ∩ Zd ) \ B with high multiplicity i.e. λγ = 22 . Since
P
d
γ ∈ S, there is a x ∈ Rd+1
i=0 xi = 1 and γ = x0 B0 + x1 B1 + . . . xd Bd . By Theorem 7
≥0 with
O(d)

> 1 such that Level(Kx) = 1. According to Lemma 1,
there exists a multiplicity K = 22
P
d
there exists a δ ∈ S ∩ Z≥0 such that Kγ = δ + di=0 Λi Bi for some Λ ∈ Zd+1
≥0 . Then we can
P
d+1
′
′
construct a λ ∈ Z≥0 with b = s∈S∩Zd λp p, which has more weight in B as K > 1:
λ′ =



λγ − K




λ + 1
δ


λBi + Λi




λ
s

∀Bi ∈ B
∀s ∈ (S ∩ Zd ) \ (B ∪ {γ, δ})

Since K > 1, the resulting vector λ′ has a decreased vertex distance as the sum p∈(P∩Zd )\VI λp
is reduced at least by 1. Using Theorem 1 applied to components i ∈ (S ∩ Zd ) \ B, we can
construct a λ′′ with |supp(λ′′ \ B)| ≤ 2d . In the case that there is another component γ ∈
Ω(d)
we can iterate this process. In the other case, solution
(S ∩ Zd ) \ B with multiplicity λ′′γ = 22
′′
λ fulfills the proposed properties.
P

Proof of the structure Theorem 5
Proof. Given polytope P = {x ∈ Rd | Ax ≤ c} for some matrix A ∈ Zm×d and a vector c ∈ Zd
and let PI be the integer polytope with vertices VI . The structure theorem follows easily by
decomposing the polytope P into simplices S of the form S = Conv(B0 , B1 , . . . Bd ) for Bi ∈ Vi .
By Caratheodory’s Theorem, there exist for each γ ∈ P vertices B0 , B1 , . . . , Bd ∈ VI and a x ∈
Pd
d
Rd+1
i=0 xi = 1 such that γ = x0 B0 +. . .+xd Bd . Consider the vector b ∈ int.cone(P ∩Z ).
≥0 with
d

Let λ ∈ ZP∩Z be the integral vector with b =
2d

p∈P∩Zd λp p.
2d simplices

P

By Theorem 1, we can assume
(k)

(k)

that supp(λ) ≤
and hence there are at most
S (k) = Conv(B01 , B1 , . . . Bd )
d
for k = 1, . . . , 2 which contain a point γ ∈ P with λγ > 0. Finally, we can apply our main
P∩Zd which fulfills
Theorem 3 to every simplex S (k) for k = 1, . . . , 2d to obtain a vector λ′ ∈ Z≥0
the above properties.

2.1 Algorithmic application
Computing VI in fpt-time
Given Polytope P = {x ∈ Rd | Ax ≤ c} for some matrix A ∈ Zm×d and a vector c ∈ Zd
such that all coefficients of A and c are bounded by ∆. Cook et al. [CHKM92] proved that
the number of vertices VI of the integer polytope PI is bounded by md · O((log ∆))d . In the
following we give a brief description on how the set of vertices VI can be computed in time
|VI | · dO(d) · (m log(∆))O(1) and therefore in fpt-time parameterized by the number of vertices
|VI |. For a detailed description of the algorithm we refer to the thesis of Hartmann [Har89].
Given at timestep t a set of vertices Vt ⊂ VI and the set of facets F (t) = {F1 , . . . , Fℓ } of
conv(Vt ) corresponding to half-spaces Hi = {x | ni x ≤ ci } for normal vectors n1 , . . . , nℓ ∈ Rd
and constants c1 , . . . , cd ∈ Z with conv(V ) = ∩ℓi=1 Hi . Consider for every 1 ≤ i ≤ ℓ the polytope
P ∩ Hi− for a halfspace Hi− = {x | x ∈ P, ni x ≥ ci }. Compute with Lenstra’s algorithm [LJ83]
a solution x∗ ∈ P ∩ Zd of the ILP max{ni x | x ∈ (P ∩ Zd), ni x ≥ ci }. In the case that ni x∗ > ci ,
solution x∗ does not belong to Conv(Vt ). Assuming that x∗ is a vertex of the integer polytope
of P ∩ Hi− , solution x∗ is also a vertex of the integer polytope PI . We can add x∗ to the set

8

of existing vertices Vt ⊂ VI , construct the increased set of facets F (t+1) of Conv(Vt ∪ {x∗ }) and
iterate the procedure. In the case that there is no solution x∗ with ni x∗ > ci for any 1 ≤ i ≤ ℓ,
we have that PI = Conv(Vt ) and are done.
Bin Packing in fpt-time
In the following we describe the algorithmic use of the presented structure theorem 5. Therefore,
we follow the approach by Goemans and Rothvoß [GR14].
Theorem 8. Given polytopes P, Q ⊂ Rd , one can find a y ∈ int.cone(P ∩ Zd ) ∩ Q and
2O(d) enc(P)O(1) enc(Q)O(1) , where
P∩Zd such that b = P
a vector λ ∈ Z≥0
pP∩Zd λp p in time |VI |
enc(P), enc(Q) is the encoding length of the polytope P, Q or decide that no such y exists.
Proof. Let P = {x ∈ Rd | Ax ≤ c} and Q = {x ∈ Rd | Ãx ≤ c̃} be the given polytopes
˜
for a matrix A ∈ Zm×d and a matrix Ã ∈ Zm̃×d . First, we compute the set of vertices of
O(d)
enc(P)O(1) enc(Q)O(1) as described above. Suppose that there is a vector
PI in time |VI |2
P∩Zd with
b ∈ int.cone(P ∩ Zd ) ∩ Q, then by Theorem 5, we know there is a vector λ ∈ Z≥0
P
b = p∈P∩Zd λs s such that
O(d)

1. λp ≤ 22

∀p ∈ (P ∩ Zd ) \ VI ,

2. |supp(λ) ∩ VI | ≤ d · 2d ,
3. |supp(λ) \ VI | ≤ 22d .
I|
At the expense of a factor |V
we can guess the support Vλ ⊆ VI of λ restricted to
= |VI |2
d2d
components λp with p ∈ VI i.e. Vλ = supp(λ)∩ VI . For each p ∈ Vλ we use variables λ̄p ∈ Z≥0 to
determine the multiplicities of λp . Furthermore, we guess the number of different points p 6∈ Vi
(j)
used in λ i.e. k = |supp(λ) \ VI | ≤ 22d . We use variables xi for j = 1, . . . , k to determine
the points p 6∈ VI and their multiplicity λp . Note that in the following ILP, we encode the
(j)
multiplicity of a λp with p 6∈ VI binary, therefore the number of variables xi can be bounded
O(d)
) = 2O(d) . And finally we use a vector y ∈ Zd to denote the target vector in
by 22d · log(22
polytope Q.
O(d)



(j)

≤b

(j)

=y

Axi

∀i = 1, . . . , 2O(d) and ∀j = 1, . . . , k

O(d)

X

p∈Vλ

λ̄p p +

k 2X
X

2j xi

j=1 i=1

Ãy ≤ b̃
xi ∈ Zd

i = 1, . . . , k

λ̄p ∈ Z≥0

∀p ∈ Vλ

y∈Z

d

Using the algorithm of Lenstra or Kannan ([LJ83],[Kan87]) to solve the above ILP which
has k2O(d) + d + d2d = 2O(d) variables and mk + d + m̃ + d|Vλ | = m2O(d) + m̃ constraints,
O(d)
¯ =
¯ O(1) = 22O(d) enc(P)O(1) enc(Q)O(1) , where ∆
· (m2O(d) + m̃)O(1) log(∆)
takes time (2O(d) )2
O(d)
O(d)
O(1)
d
2
2
˜
enc(P)
enc(Q)O(1)
, d!∆ , ∆}. The total running time is hence of the form: |VI |
max{2
!

x
We can apply this theorem to the bin packing problem by choosing P = {
∈ Rd+1
≥0 |
1
sT x ≤ 1} and Q = {b} × [0, a] to decide if items b can be packed into at most a bins. Using

9

binary search, on the number of used bins, we can solve the bin packing problem in time
O(d)
· log(∆)O(1) , where ∆ is the largest multiplicity of item sizes or the largest denominator
|VI |2
appearing in an itemsize s1 , . . . , sd . Since |VI | ≥ d+1 this running time is fpt-time, parametrized
by the number of vertices |VI | and therefore we obtain Theorem 6.

3 Lower Bound
In this section we give a construction of a bin packing instance (s, b) with vertex distance
Ω(d)
Dist(b) = 22 . We consider the case that all item sizes s1 , . . . , sd are of the form si = a1i
for some ai ∈ Z≥1 . In this case, all vertices of the knapsack polytope P = {x ∈ R≥0 |
s1 x1 + . . . + sd xd ≤ 1} are of the form Bi = (0, . . . , 0, ai , 0, . . . , 0)T and therefore integral. We
obtain that PI = P = Conv(0, B1 , . . . , Bd ).
Our approach for the proof of the lower bound is as follows: We prove the existence of a
parallelepipped Π = {x1 B1 + . . . + xd Bd | xi ∈ [0, 1]} with a special element g ∈ (P ∩ Zd ) \ VI
such that the unique optimal packing of the bin packing instance K · g (for a possibly large
multiplicity K ∈ Z≥0 ) is to use K times the configuration g. In this case, weight can not
be shifted to the vertices B1 , . . . , Bd and hence the instance Kg implies a vertex distance of
Dist(Kg) = K. We show that the special element g can be determined by a set of modulo
congruences. Therefore, we are able to use basic number theory to construct a bin packing
instance with double exponential vertex distance.
First, we take a close look at the parallelepipped Π and Cone(B). Recall that two points
b, b′ ∈ Cone(B) are equivalent if [b] = [b′ ]. Each point b ∈ Cone(B) is equivalent to a point in
the parallelepiped Π.
Lemma 4. Using operation + defined by p + p′ = [p + p′ ] for some p, p′ ∈ Π ∩ Zd then
G(Π) = (Π ∩ Zd , +) is an abelian group with |G(Π)| = |det(B)| many elements.
The proof that G(Π) is a group can be easily seen, since G(Π) is the quotient group of Zd
and the lattice ZB1 ⊕ . . . ⊕ ZBd . For the fact that |G(Π)| = det(B) we refer to [Bar07]. In the
considered case that Bi = (0, . . . , 0, ai , 0, . . . , 0)T , the group G(Π) is isomorphic to (Z/a1 Z) ×
. . . × (Z/ad Z). Recall that the set P ∩ Zd ⊂ Π ∩ Zd represents all integral points of the knapsack
polytope and each δ ∈ P ∩ Zd therefore represents a way of packing a bin with items from sizes
s1 , . . . , sd . We call δ ∈ P ∩ Zd a configuration.
In the following subsection 3.3, we also give an easy observation on how the vertex distance
is connected to the integrality gap of the bin packing problem.

3.1 Preliminaries
In this section we state some basic number theoretic theorems that we will use in the following.
For details and proofs, we refer to the books of Stark [Sta70] and Graham, Knuth and Patashnik
[GKP94].
Theorem 9 ([Sta70]). Let a1 , . . . ad ∈ Z with gcd(a1 , . . . , ad ) = 1, then there exist v1 , . . . , vd ∈ Z
such that
a1 v1 + . . . ad vd = 1.
Theorem 10 (Chinese remainder theorem [Sta70]). Suppose a1 , . . . , ad ∈ Z are pairwise coprime. Then, for any given sequence of integers i1 , . . . , id , there exists an integer x solving the
following system of simultaneous congruences.
x ≡ ij
Furthermore, x is unique

mod

mod aj for 1 ≤ j ≤ d.

Qd

i=1 ai .

10

Theorem 11 ([Sta70]). Given congruence x mod a. If x and a are coprime, there exists an
inverse element x−1 ∈ Z/aZ such that xx−1 ≡ 1 mod a.
Sylvester’s sequence is defined by,
S1 = 2
Sj = 1 +

j−1
Y

Si

i=1

and has following properties (see [GKP94])
n

Sn ≈ 1.2642
j−1
X
i=1

1
1
=1−
Si
Sj − 1

3.2 Proof of the lower bound
We start by defining the size of an element π ∈ Π by
Size(π) =

d
X

s i πi .

i=1

In our case, the sizes si are given by si = a1i and vectors Bi = (0, . . . , 0, ai , 0, . . . , 0)T for some
ai ∈ Z≥1 . Hence, the size of a Bi equals to 1 and for each x ∈ [0, 1)d with Bx = π, we have that
Pd
Since the matrix B is a diagonal matrix with entries ai , the determinant
i=1 xi = Size(π).
Qd
equals det(B) = i=1 ai . We define for 1 ≤ i ≤ d that
Ri =

det(B) Y
=
aj .
ai
j6=i

In the following lemma we show that the fractional value of the size {Size(Π)} is unique for
every element π ∈ G(Π).
Lemma 5. Given parallelepiped Π = {x1 B1 +. . .+xd Bd | xi ∈ [0, 1)d } with Bi = (0, . . . , 0, ai , 0, . . . , 0)T .
If a1 , . . . , ad are pairwise coprime, then for every 0 ≤ a < det(B), there exists a unique vector
π ∈ Π ∩ Zd and a vector x ∈ [0, 1)d with Bx = π, such that
Size(π) =

d
X

xi = z + a/det(B),

i=1

for some z ∈ Z≥0 .
Q

Proof. Since a1 . . . , ad are pairwise coprime, we have that gcd(Ri , Ri+1 ) = j6=i,i+1 aj and
hence gcd(R1 , . . . , Rd ) = 1. By Theorem 9, there exist v1 , . . . , vd ∈ Z such that v1 R1 + . . . +
P
vd Rd = 1. For vi′ = vi Ri mod det(B) the sum di=1 vi′ ≡ 1 mod det(B). Consider the vector
P
P
vd′
vi′
v1′
1
, . . . , det(B)
)T , then di=1 xi = di=1 det(B)
= det(B)
+ z for some z ∈ Z≥0 . The vector
x = ( det(B)
Bx =

v1′
det(B) B1

+ ... +

vd′
det(B) Bd

is integral since for every 1 ≤ i ≤ d the congruence vi′ ai ≡
v′

i
ai ∈ Z≥0 .
vi Ri ai ≡ vi det(B) ≡ 0 mod det(B) holds and hence each item sizes ai xi = πi = det(B)
Consider multiplicities x, 2x, 3x, . . .. As above we can rewrite each element Kx ∈ Rd≥0 by
Kx = Kxint + {Kx} with {Kx} = ({Kx1 }, . . . , {Kxd })T and {Kxi } < 1, which implies
that B({Kx}) ∈ Π. Since B(Kx) is integral and B(Kxint ) is integral, the vector B({Kx})

11

is integral as well. Furthermore, the sum of all component {Kx} sums up to di=1 {Kxi } =
P
P
K
+ z, for some z ∈ Z≥0 . Hence for each multiplicity Kx in
K di=1 xi − di=1 ⌊Kxi ⌋ = det(B)
P

K
0x, x, 2x, . . . , (det(B)−1)x there is a vector B({Kx}) ∈ Π with di=1 {Kxi } = z+ det(B)
and since
Π contains exactly det(B) many elements (see Lemma 4), each element of G(Π) corresponds to
a unique element of 0x, x, 2x, . . . , (det(B) − 1)x.

P

Consider the specific element g ∈ Π ∩ Zd with fractional vector x ∈ [0, 1)d such that Bx = g
and Size(g) = det(B)−1
det(B) + z. We call g the full generator of the group G(Π).
Corollary 1. For every element π ∈ G(Π) there exists a multiplicity K such that Kg = π, i.e.
the full generator g generates the group Π and hence G(Π) =< g > is a cyclic group. Element
Kg ∈ Π has a size of z + det(B)−K
for some z ∈ Z≥0 .
det(B)
Proof. In the proof of the lemma above, we showed that the element Bx with

Pd

i=1 xi

1
= z+ det(B)

K
.
generates G(Π) as each multiplicity Kx of x yields an element B({Kx}) ∈ G(Π) of size z+ det(B)

We consider the full generator g with g = Bx′ for some x′ with di=1 x′i = z + det(B)−1
det(B) for
some z ∈ Z≥0 . By the same argument as before, the multiplicities Kx′ yield elements π ′ =
for some z ∈ Z≥0 .
B({Kx′ }) ∈ G(Π) with Size(π ′ ) = z + det(B)−K
det(B)
P

As above, we consider multiplicities Kg of a vector g ∈ Π and some K > 0. We say that
Kg ∈ cone(B) is unique if g ∈ P and 2g, . . . , Kg 6∈ P i.e. g is a configuration and 2g, . . . , Kg
are not. In the following lemma we prove that if Kg is unique and g is a full generator, then
using K-times configuration g is the unique optimal packing for instance Kg.
Lemma 6. Let g be the full generator of G(Π). If Kg ∈ cone(B) is unique, then there is no
(P∩Zd )

λ ∈ Z≥0

with λg 6= K such that

P

p∈P∩Zd

λp p = Kg and |λ| = K.

Proof. Consider bin packing instance Kg ∈ cone(B) and a packing of the instance into bins
1, . . . , K. Since g contains items of size det(B)−1
det(B) , items in instance Kg have a total size of
K
K det(B)−1
det(B) and therefore, the bins 1, . . . , K have total free space of det(B) . Each bin configuration
c1 , . . . , cK of bins 1, . . . , K belongs to P and hence to Π(G). By Cororllary 1 for each ci there
exists a multiplicity Ki ∈ Z≥1 such that Ki g = ci . Assuming that ci 6= g and hence Ki > 1
we know that Ki > K as by definition of the uniqueness of Kg, elements 2g, . . . , Kg are no
configurations. However, a bin with configuration Ki g = ci ∈ P with Ki > K has free space
K′
K
det(B) > det(B) and hence more free space than the total sum of free space in bins 1, . . . , K.
Therefore, a configuration 6= g can not appear in an optimal packing of the instance Kg. The
unique way of packing instance Kg into K bins is to use K times configuration g.

Consider the full generator g = x1 B1 + . . . + xd Bd ∈ P with xi ≥ 0, we say g has the long-run
property if (1 − ǫ) S1i ≤ xi < S1i for 1 ≤ i ≤ d − 1 and some ǫ < ( Sd1−1 )2 , where Si is the i-th
sylvester number. The following inequality gives a lower bound for kxk1 :
d−1
X

xi ≥ (1 − ǫ)

i=1

d−1
X
i=1

>1−

1
1−ǫ
1
= (1 − ǫ)(1 −
)=1−ǫ−
Si
Sd − 1
Sd − 1

1
1
1
1
1
1
−
=1−
+
−
>1−
(Sd − 1)2 Sd − 1
(Sd − 1)2
(Sd − 1)(Sd − 2) Sd − 2
Sd − 2

If g is a configuration and hence kxk1 ≤ 1, we can bound xd from above by
xd ≤ 1 −

d−1
X

xi <

i=1

1
Sd − 2

Recall that the following statements are equivalent:

12

• {Kg} ∈ G(Π) is a configuration i.e. Kg ∈ P
• Level(Kx) = 1
Lemma 7. If g is a configuration and g has the long run property, then (Sd − 2)g is unique for
d ≥ 3.
Proof. Let x ∈ [0, 1]d+1 such that x0 0 + x1 B1 + . . . + xd Bd = g with di=0 xi = 1. We consider
the level Level(Kx) of multiplicities of x. Recall that Level(Kx) = 1 if and only if {Kg} ∈ Π is
a configuration. Hence, it remains to prove that that Level(Kx) > 1 for every 1 < K ≤ Sd − 2.
By Lemma 2 we know that level Level(Kx) = Level((K − 1)x) − JK + 1, where JK is the
number of jumps at K. This implies by induction that Level(Kx) = K − J, where J is the total
P
1
1
sum of all jumps in 2x, . . . , Kx. Using that d−1
i=1 xi > 1 − Sd −2 , we obtain that x0 , xd < Sd −2
and hence Kx0 , Kxd < 1 for K ≤ Sd − 2. This means that component 0 and component d do
not jump in 2x, . . . , (Sd − 2)x.
P

Observation 3. For every 1 ≤ i ≤ d − 1, component i jumps at 1 + Si , 1 + 2Si , 1 + 3Si , . . . , 1 +
⌋Si .
⌊ SdS−2
i
Since (1 − ǫ) S1i ≤ xi <

1
Si

for 1 ≤ i < d we know on the one hand that M Si xi < M and on the

other hand (1 + M Si )xi ≥ (1 − ǫ)( S1i + M ) > M as ǫ( S1i + M ) ≤ ǫ( 1+(SSdi −2) ) <

Sd −1 1
(Sd −1)2 Si

<

1
Si

. Hence component i jumps at 1 + Si from 0 to 1 and at 1 + 2Si from
for i ≤ d − 1 and M ≤ SdS−2
i
1 to 2 and so on. The total number of jumps JK (i) in component i can therefore be bounded
by 1 + JK (i)Si ≤ K and hence JK (i) ≤ ⌊ K−1
Si ⌋.
The total number of jumps J up to K ≤ Sd − 2 in components 0, . . . , d sums up to
J=

d
X
K −1

⌊

i=0

Since

Pd−1

1
i=1 Si

=1−

1
Sd −1

Si

⌋=

d−1
X

⌊

i=1

d−1
X 1
K −1
⌋ ≤ ⌊(K − 1)
⌋
Si
S
i=1 i

we obtain for K ≤ Sd − 2

J ≤ ⌊(K − 1)

d−1
X
i=1

1
1
⌋ = ⌊(K − 1)(1 −
)⌋ ≤ K − 2
Si
Sd − 1

which implies that Level(Kx) = K − J ≥ K − (K − 2) = 2 and therefore {Kg} 6∈ P for
K = 2, . . . , Sd − 2.
Lemma 8. An element g ∈ G(Π) is a full generator if and only if for all 1 ≤ i ≤ d
gi ≡ −Ri−1

mod ai .

Proof. Consider the full generator g of a group G(Π). By definition of the full generator, we
obtain that there exists a z ∈ Z≥0 such that
Size(g) =

d
X
i=1

si gi =

d
X
gi
i=1

ai

=z+

det(B) − 1
det(B)

and hence
det(B) − 1 + z · det(B) = det(B)

d
X
gi
i=1

13

ai

=

d
X
i=1

Ri gi

By definition of the modulo operation this equation is equivalent to
d
X

Ri gi ≡ det(B) − 1 mod (det(B)).

(1)

i=1

As det(B) − 1 ≡ −1 mod ai for each 1 ≤ i ≤ d, we obtain by the Chinese remainder Theorem
10 (assuming that all ai ’s are coprime), that congruence (1) is equivalent to the following system
of congruences:
d
X

Ri gi ≡ −1 mod ai

for 1 ≤ i ≤ d

i=1

As Ri ≡ 0 mod aj for any i 6= j, we obtain that
gi ≡ −Ri−1

Pd

i=1 Ri gi

≡ Rj gj mod aj and hence

mod ai .

i

Sylvester’s sequence Si grows double exponentially by approximately Si ≈ 1.2642 and thereΩ(i)
fore Si = 22 . It remains to prove the existence of sizes s1 , . . . , sd with group G(Π) such that
the full generator of G(Π) has the long-run property. The following theorem concludes the proof
of a double exponential lower bound.
Theorem 4. There exists a bin packing instance with sizes a11 , . . . , a1d for ai ∈ Z≥1 and multiplicities b ∈ Zd≥0 corresponding to a point b ∈ int.cone(P ∩Zd ), where P is the knapsack polytope
such that
Ω(d)

Dist(b) ≥ Sd − 2 = 22

Proof. Given parallelepiped Π = {x1 B1 + . . . + xd Bd | xi ∈ [0, 1)} with configurations Bi =
(0, . . . , 0, ai , 0, . . . , 0)T . Assume there are sizes si such that group
! G(Π) with full generator
1
g ∈ P has the long-run property. Then K times configuration
is by Lemma 6 the unique
g
K
representation of the vector b =
Kg
B0′

=

(1, 0, . . . , 0)T

and

Bi′

=

!

∈ int.cone(P ′ ∩ Zd ) where P ′ = Conv(B0′ , . . . , Bd′ ) with

!

1
. According to Lemma 7 this implies a vertex distance of
Bi

Ω(d)

Dist(b) = Sd − 2 = 22 . Therefore, it remains to prove the existence of sizes s1 , . . . , sd with
group G(Π) such that the full generator g of G(Π) has the long-run property. In the following
we give an inductive construction of the sizes si = a1i :
1
1
First, choose a1 arbitrarily such that there is an m1 with (1 − ǫ) S11 ≤ m
a1 < S1 . This is
possible for every a1 > Sǫ1 that is not a multiple of S1 = 2. In this case m1 can be chosen
1⌋
1⌋
1 )−1
< S11 and ⌊a1a/S
≥ (a1 /S
≥ S11 − a11S1 ≥ (1 − ǫ)S1 .
by m1 = ⌊ Sa11 ⌋ and we obtain ⌊a1a/S
a1
1
1
Additionally, we assume w.l.o.g. that m1 and a1 are coprime.
1
1
i+1
≤m
For 1 ≤ i < d choose ai+1 such that there exists an mi+1 with (1 − ǫ) Si+1
ai+1 < Si+1 . The
existence of the mi+1 can be shown for any ai+1 > Si+1
that is not a multiple of Si+1 by the
ǫ
same argument as above for m1 . Additionally we choose ai+1 such that the following conditions
hold:
ai+1 ≡ (

i−1
Y

aj )−1 · (−mi )−1

j=1

14

mod ai

(2)

ai+1 ≡ 1 mod aj for j = 1, . . . , i − 1

(3)

Remark the following points, where we use the fact that gcd(a, b) = gcd(a mod b, b) for numbers
a, b ∈ Z.
• The inverse element of i−1
j=1 aj and −mi in Z/ai Z exists since a1 , . . . aj are coprime to ai
and mi is coprime to ai (see Theorem 11),
Q

• since a1 , . . . ai are coprime, by the chinese remainder theorem 10, there exists a unique
Q
element ai+1 mod ( ij=1 aj ) satisfying the above inequalities,
• condition (2) implies that ai+1 is coprime to ai as mi is coprime to ai and
coprime to ai (coprimeness carries over to the inverse),

Qi−1

j=1 aj

is

• condition (3) implies that ai+1 is coprime to a1 , . . . , ai−1 .
Claim (1). The full generator g of the constructed group G(Π) has the long-run property.
To prove that g = x1 B1 + . . . + xd Bd has the long-run property, we show for all 1 ≤ i < d
that S1i (1 − ǫ) ≤ agii < S1i . By Lemma 8
gi ≡ −Ri−1

mod ai

By construction of the ai we obtain for g1 , . . . , gd−1 the following congruences


gi ≡ − 
≡ mi

i−1
Y

j=1

d
Y

aj ·

j=i+1

mod ai

−1

aj 

(2)



≡ −

i−1
Y

j=1

−1

aj · ai+1 

(3)



≡ − (

i−1
Y

aj ) · (

j=1

i−1
Y

j=1

mod aj :
−1

aj )−1 · (−mi )−1 

Since for every δ ∈ Π we have that δi < ai , we know gi = mi . By definition of mi we obtain
1
i
(1 − ǫ) S1i ≤ xi = m
ai < Si , which proves Claim 1.
Claim (2). The full generator g is a configuration.
Suppose Level(x) > 1, then we know by Lemma 5 that
z ∈ Z≥1 .
d
X
i=1

xi <

d−1
X
i=1

Pd

i=1 xi

= z+

det(B)−1
det(B)

1
1
1
+ xd = (1 −
) + xd < (1 −
)+1
Si
Sd − 1
Sd − 1

Since xi = agii < S1i for 1 ≤ i < d, we know that ai ≥ Si + 1 and hence det(B) >
Qd−1
i=1 (Si + 1) > Sd − 1 which implies:
d
X
i=1

for some

xi < (1 −

1
det(B) − 1
)+1=1+
det(B)
det(B)

This is a contradiction to Level(x) > 1.

15

Qd−1
i=1

ai >

3.3 Relation between Dist and the IRUP
In this section we study briefly the connection between the vertex distance and the modified
integer roundup property (MIRUP) which is defined in the following. Let P = {x ∈ Rd≥0 |
sT x ≤ 1} be the knapsack polytope for given sizes s1 , . . . sd ∈ (0, 1]. For given multiplicities
a1 , . . . , ad , a packing of the items into a minimum number of bins is given by a solution of the
following ILP:
min{kλk1 |

X

λp p = b, λ ∈ Zd≥0 }.

(4)

λp p = b, λ ∈ Rd≥0 }.

(5)

p∈P∩Zd

The relaxed linear program (LP) is defined by
min{kλk1 |

X

p∈P∩Zd

Let λ∗ be an optimal solution of the ILP (4) and let λf be an optimal solution of the relaxed
linear program (5), then the integrality gap of an instance (s, b) is defined by:
kλk1 − λf

1

A well known conjecture by Scheithauer and Terno [ST97] concerning the integrality gap for
bin packing instance is that for any instance I, we have that kλ∗ k1 ≤ ⌈ λf ⌉ + 1 which is the
1
so called modified integer roundup property (MIRUP). The integer roundup property (IRUP)
is fulfilled if kλ∗ k1 ≤ ⌈ λf ⌉. In general, bin packing instances where die IRUP is not fulfilled
1
appear rarely. In the literature those kind of instances are studied and constructions of instances
are given where die IRUP does not hold (see [ST97], [CDDDIR14]). In the following we show
that a bin packing instance with a large vertex distance Dist(b) implies the existence of many
subinstances where the IRUP does not hold. Specifically, we show the following theorem:
Theorem 12. Given a bin packing instance (s, b) corresponding to a vector b ∈ int.cone(P ∩Zd )
P
d
with vertex distance Dist(b) and let λ ∈ ZP∩Z be a solution with p∈P∩Zd λp p = b and vertex
P
distance p∈(P∩Zd )\VI λp = Dist(b). For every γ ∈ (P ∩ Zd ) \ VI with λγ = d + Z for some
Z ∈ Z≥0 , there exist at least Z instances where the IRUP does not hold.
Proof. Given an instance b ∈ int.cone(P ∩ Zd ) with Dist(b). Then there exists an integral
P
P
d
optimal solution λ ∈ ZP∩Z with p∈P∩Zd λp p = b and p∈(P∩Zd )\VI λp = Dist(b). We consider
for a γ ∈ (P ∩Zd )\VI with λγ = d+Z for some Z ∈ Z≥1 the instances (d+1)γ, . . . , (d+Z)γ. Let
b′ ∈ int.cone(P ∩ Zd ) be the vector corresponding to a multiplicity (d + Z ′ )γ for a Z ′ ≤ Z. Note
that by definition of b′ , we have that Dist(b′ ) = d + Z ′ , as γ is chosen from (P ∩ Zd) \ VI and the
existence of a solution λ′′ for b′ with smaller vertex distance would imply a small vertex distance
for b. Since b′ ∈ Cone(P ∩ Zd ), there exist a basic feasible solution λf ∈ Rd≥0 corresponding to
vectors B1 , . . . , Bd ∈ P ∩ Zd of LP (5) with b′ = λf1 B1 + . . . + λfd Bd and λf ≤ d + Z ′ . Using
1
Caratheodory’s theorem, we can assume w.l.o.g. that B1 , . . . , Bd are vertices.
Claim: The vector [b′ ] = {λf1 }B1 + . . . + {λfd }Bd does not fulfill the integer roundup property.
Suppose the roundup property for [b′ ] is fulfilled, then there exists a packing of instance [b′ ] into
int
int
=
⌈ {λf } ⌉ bins. Using the decomposition of b′ = Bλf + [b′ ] into an integral part Bλf
1

⌊λf1 ⌋B1 +. . .+⌊λfd ⌋Bd and the fractional part [b′ ], we obtain a packing for b′ into ⌈ λf

1

⌉ ≤ d+Z ′

bins (which implies optimality). The constructed packing has vertex distance of ≤ ⌈ {λf } ⌉.
1

Since ⌈ {λf } ⌉ ≤ d < d + Z ′ = Dist(b′ ), this is a contradiction to the minimality of the vertex
1
distance for b′ .

16

Claim: Let vectors b(1) , b(2) ∈ int.cone(P ∩ Zd ) be given which correspond to multiplicities
K1 γ and K2 γ of vector γ ∈ (P ∩ Zd ) \ VI with K1 < K2 . Then [b(1) ] 6= [b(2) ].
By a similar argument as in the previous claim, we can argue in this case. Since b(1) , b(2) ∈
Cone(P ∩ Zd ), there exist basic feasible solutions λ(1) , λ(2) ∈ Rd≥0 corresponding to vectors
(i)

(i)

B1 , . . . , Bd ∈ VI of LP (5) with b(i) = λ1 B1 + . . . + λd Bd for i = 1, 2 and λ(1) ≤ λ(2)
as K1 γ ≤ K2 γ. Suppose that [b(1) ] = [b(2) ], then we obtain for the difference (K2 − K1 )γ
int
int
int
int
corresponding to b(2) − b(1) = Bλ(2) + [b(2) ] − Bλ(1) − [b(1) ] = Bλ(2) − Bλ(1) . Therefore,
the difference b(2) −b(1) can be written by the (positive) sum of vertices B1 , . . . , Bd . This implies
a packing for b(2) by b(2) = b(1) + (b(2) − b(1) ) with vertex distance Dist(b(1) ) < Dist(b(2) ) which
contradicts the minimality of vertex distance b(2) .
As a conclusion of the above claims, we obtain for each multiplicity (d + 1)γ, . . . , (d + Z)γ of
γ the instances [(d + 1)γ], . . . , [(d + Z)γ] ∈ G(Π), where die IRUP does not hold.
Note that an instance with large vertex distance (e.g. double exponential in d) implies the
existence of solutions with large (double exponential) multiplicities λγ as the number of nonzero components can be bounded by the theorem of Eisenbrand and Shmonin [ES06] applied
to points in (P ∩ Zd ) \ VI .
Together with the construction of the previous subsection where we created a bin packing
Ω(d)
for some γ ∈ P ∩ Zd ,
instance b with a unique solution λ ∈ int.cone(P ∩ Zd ) with λγ = 22
we obtain that b has double exponentially many subinstances where the IRUP is not fulfilled.

References
[Bar07]

A. Barvinok. “Lattice points, polyhedra, and complexity”. In: Geometric Combinatorics, IAS/Park City Mathematics Series 13 (2007), pp. 19–62.

[CDDDIR14]

Alberto Caprara, Mauro Dell’Amico, José Carlos Dı́az-Dı́az, Manuel Iori, and
Romeo Rizzi. “Friendly bin packing instances without Integer Round-up Property”. In: Mathematical Programming 150.1 (2014), pp. 5–17.

[CHKM92]

W. Cook, M. Hartmann, R. Kannan, and C. McDiarmid. “On integer points in
polyhedra”. English. In: Combinatorica 12.1 (1992), pp. 27–37. doi: 10.1007/BF01191202.

[DF99]

R. G. Downey and M. R. Fellows. Parameterized Complexity. Monographs in
Computer Science. Springer, 1999. isbn: 978-1-4612-6798-0.

[ES06]

F. Eisenbrand and G. Shmonin. “Carathéodory bounds for integer cones”. In:
Operation Research Letters 34.5 (2006), pp. 564–568.

[GKP94]

Ronald L. Graham, Donald E. Knuth, and Oren Patashnik. Concrete Mathematics: A Foundation for Computer Science. 2nd. Boston, MA, USA: AddisonWesley Longman Publishing Co., Inc., 1994. isbn: 0201558025.

[GR14]

M. X. Goemans and T. Rothvoß. “Polynomiality for Bin Packing with a Constant
Number of Item Types”. In: Symposium on Discrete Algorithms, SODA. 2014,
pp. 830–839.

[Har89]

M. Hartmann. “Cutting planes and the complexity of the integer hull”. In:
School of Operations Research and Industrial Engineering, Cornell University
(1989).

[HL83]

A.C. Hayes and D.G. Larman. “The vertices of the knapsack polytope”. In:
Discrete Applied Mathematics 6.2 (1983), pp. 135 –138.

[HR15]

R. Hoberg and T. Rothvoss. “A Logarithmic Additive Integrality Gap for Bin
Packing”. In: CoRR abs/1503.08796 (2015).

17

[JS11]

K. Jansen and R. Solis-Oba. “A Polynomial Time OPT + 1 Algorithm for
the Cutting Stock Problem with a Constant Number of Object Lengths”. In:
Mathematics of Operations Research 36.4 (2011), pp. 743–753.

[Kan87]

R. Kannan. “Minkowski’s Convex Body Theorem and Integer Programming”.
In: Mathematics of Operations Research 12.3 (1987), pp. 415–440.

[KK82]

N. Karmarkar and R.M. Karp. “An Efficient Approximation Scheme for the OneDimensional Bin-Packing Problem”. In: 23rd Annual Symposium on Foundations
of Computer Science (FOCS). IEEE Computer Society, 1982, pp. 312–320.

[LJ83]

H. W. Lenstra and Jr. “Integer programming with a fixed number of variables”.
In: Mathematics of Operations Research 8.4 (1983), pp. 538–548.

[Onn15]

S. Onn. “Unimodular Integer Caratheodory is Fixed Parameter Tractable”. In:
CoRR abs/1511.03403 (2015).

[Rot13]

T. Rothvoss. “Approximating Bin Packing within O(log OPT * Log Log OPT)
Bins”. In: 2013 IEEE 54th Annual Symposium on Foundations of Computer
Science 0 (2013), pp. 20–29.

[Sch86]

Alexander Schrijver. Theory of Linear and Integer Programming. John Wiley &
Sons, Inc., 1986. isbn: 0-471-90854-1.

[ST97]

G. Scheithauer and J. Terno. “Theoretical investigations on the modified integer round-up property for the one-dimensional cutting stock problem”. In:
Operations Research Letters 20.2 (1997), pp. 93 –100.

[Sta70]

H.M. Stark. An introduction to number theory. Markham mathematics series.
Markham Pub. Co., 1970.

18

