Algorithms for the Bin Packing Problem
with Overlapping Items
Aristide Grange∗

Imed Kacem∗

Sébastien Martin

∗

arXiv:1605.00558v3 [cs.DS] 5 Sep 2017

September 6, 2017

Abstract

1

Introduction

Over the last decade, the book (as a physical object)
has given ground to the multiplication of screens of
all sizes. However, the page arguably remains the
fundamental visual unit for presenting data, with
degrees of dynamism varying from video to static
images, from infinite scrolling (e.g., Windows Mobile interface) to semi-permanent display without
energy consumption (e.g., electronic paper). Pagination is to information what Bin Packing is to
matter. Both ask how to distribute a given set of
items into the fewest number of fixed-size containers. But where Bin Packing generally handles
concrete, distinct, one-piece objects, Pagination
processes abstract groups of data: as soon as some
data are shared by two groups packed in the same
container, there is no need to repeat it twice.

We study an extension of the bin packing problem, where packing together two or more items may
make them occupy less volume than the sum of
their individual sizes. To achieve this property, an
item is defined as a finite set of symbols from a
given alphabet. Unlike the items of Bin Packing,
two such sets can share zero, one or more symbols.
The problem was first introduced in 2011 by Sindelar et al. [19] under the name of VM Packing
with the addition of hierarchical sharing constraints
making it suitable for virtual machine colocation.
Without these constraints, we prefer the more general name of Pagination. After formulating it as
an integer linear program, we try to approximate its
solutions with several families of algorithms: from
straightforward adaptations of classical Bin Packing heuristics, to dedicated algorithms (greedy and
non-greedy), to standard and grouping genetic algorithms. All of them are studied first theoretically,
then experimentally on an extensive random test
set. Based upon these data, we propose a predictive measure of the statistical difficulty of a given
instance, and finally recommend which algorithm
should be used in which case, depending on either
time constraints or quality requirements.

1.1

Practical applications

As an introductory example, consider the following
problem. A publisher offers a collection of audio
CDs for language learning. Say that a typical CD
consists of 100 short texts read by a native speaker;
for each of them, a bilingual vocabulary of about
20 terms has to be printed out on the CD booklet. How best to do this? The most expansive option, both financially and environmentally, would
require the impression of a 100-page booklet, i.e.,
with one page per audio text. But now suppose
that each page can accommodate up to fifty terms.
If all individual vocabularies are collated into one
single glossary, no more than 100 × 20/50 = 40
pages are needed. This is the cheapest option, but
the least convenient, since it forces the consumer to
constantly leaf through the booklet while listening
to a given text. To minimize cost without sacri-

Keywords. Pagination, Bin packing, VM Packing, Integer linear programming, Heuristics, Genetic algorithms

∗ first_name.surname@univ-lorraine.fr,
LCOMS
EA7306, Université de Lorraine, Metz, FRANCE.

1

ficing usability, the publisher will be better off to
pack into each page as many individual vocabularies as possible. If there were no common term
between any two vocabularies, this problem would
be Bin Packing; but obviously, most of the time,
the vocabulary of a given text partially overlaps
with several others: this is what we propose to call
the pagination problem, in short Pagination.
In this example, it takes advantage of the fact that
the more terms are shared by two vocabularies, the
cheaper to pack them together; as an added benefit, a good pagination will tend to group on the
same page the audio texts dealing with the same
topic.
Coincidentally, it was in this context of linguistics that we first stumbled across Pagination. At
that time, we needed to display selected clusters
of morphologically related Chinese characters on a
pocket-sized screen. A full description of our initial
purpose would be beyond the scope of this paper,
and ultimately unnecessary, since the problem is
in fact perfectly general. It only differs from Bin
Packing by the nature of the items involved: instead of being atomic, each such item is a combination of elements, which themselves have two fundamental properties: first, they are all the same size
(relatively to the bin capacity); and second, their
combination is precisely what conveys the information we care about.
For instance, the members of a social network
may interest us only to the extent that they are part
of one or several friendship circles. Such groups of
mutual friends are nothing more than the so-called
cliques of a graph (Fig. 1, upper), but the cliques
are notoriously difficult to extract visually. Visualizing them as separated sets of vertices is more
effective, although quite redundant. A better compromise between compacity and clarity is attained
by paginating these sets as in Fig. 1 (lower part).
Note that, although no group is scattered across
several pages, finding all the friends of a given person may require the consultation of several pages.

1.2

6
8
1

10

11
20

2
4

13
18

3

17

15

22

5
9

14

19

25

24
21

12

7
16

23

26

17

8

10

19

13

10

12

3

26

6

2

18

1

22

16

19

24

9

4

20

11

25

5

16

7

23

19

4

14

21

15

3

Figure 1: Application of Pagination to the visualization of the cliques of a given graph. The cliques
are split over a small number of pages (here, 4)
with a given capacity (here, at most 9 vertices). To
allow each clique to be entirely contained in a single page, some vertices may be repeated on different
pages (here, 19 on 3 pages, and 3, 4, 10, 16 on 2
pages). The individual page layouts are not relevant.
Definition 1. Pagination can be expressed as the
following decision problem:
• Input: a finite collection T of nonempty finite
sets (the tiles1 ) of symbols, an integer C >
0 (the capacity) and an integer n > 0 (the
number of pages).
• Question: does there exist an n-way partition
(or pagination) P of T such that, for any tile
set (or page2 ) p of P, | ∪t∈p t| ≤ C?
Example 1. On the left of Fig. 2, T =
{{a, b, c, d, e}, {d, e, f}, {e, f, g}, {h, i, j, k}} denotes
the tiles to be distributed on pages (with respect
to a given capacity of 7). On the right, we present
4 possible such paginations of this set. For easier
reading, in the remainder of this paper, any set of
symbols (especially, a tile) defined by extension (for
instance, {w, o, r, d}) will be represented as a gray

Definition and complexity

Our problem is not just about visualization. It ex1 The fact that Pagination generalizes Bin Packing has
tends to any need of segmentation of partially reits counterpart in our terminology: the items become the
dundant data (see Section 1.3.1 for an application tiles, since they can overlap like the tiles on a roof.
2 Likewise, the move from concrete to abstract is reflected
to virtual machine colocation). Let us define it in
by the choice of the term page instead of bin.
the most general way:
2

T

t1
a b c

t2

d e f g t3
h i j k

t4

trivial

P1

a b c
d e

d e f

P2

non-optimal

a b c
d e

def g

P3
optimal

a b c
d e f

e f g
h i j k

P4
optimal

a b c
d e f g

h i j k

e f g

1.3.1

h i j k

Pagination was first introduced in 2011 by Sindelar et al. [19] in the context of virtual machine
(VM) colocation. A VM can be seen as a set of
memory pages: although most of them belong exclusively to one machine, some pages are identical
across several machines. This happens more often
as the configurations are close in terms of platform,
system version, software libraries, or installed applications. If these VM run on the same physical
server, their common memory pages can actually
be pooled in order to spare resources.
The authors study two related problems. The
first one, VM Maximization, is defined as follows: being given a collection of VM (our tiles),
each consisting in a set of memory pages (our
symbols), determine the most profitable subset
of VM that can be packed into a given set of
servers (our pages) having a capacity of k memory
pages (of C symbols). Note that, with one server,
this problem can be seen equivalently as Knapsack with Overlapping Items [8], or Densest
k-subhypergraph. Hajiaghayi et al. [10] have
proven the latter to be hard to approximate within
δ
a factor of 2(log n) for some δ > 0, and Rampersaud
and Grosu [17] approximated it by a greedy heuristic with an approximation ratio equal to the number of VM. Furthermore, when the sharing among
VM occurs in certain hierarchical fashions, Sindelar
et al. have used a left-right dynamic programming
method to devise a fully-polynomial time approximation scheme (FPTAS) [19].
The second problem, VM Packing, is nothing
else than Pagination: it demands to allocate the
VM to a minimal number of servers. Sindelar et al.
have shown that repeating their dynamic programming algorithm solves it within a O(log n) factor in
a clustered version of the hierarchical model; and
that a greedy algorithm achieves a factor of 3 when
each cluster is a singleton.
Although these hierarchical restrictions lead to
provably-good approximations algorithms, they say
nothing about the general model, which the authors
left open [19]. Thereafter, efforts have mainly focused on models and methods designed specifically
for the purposes of solving real-world VM allocation
problems (e.g., [18] with multiple resource requirements in an online setting, or [22] for approaches
based on genetic algorithms): as far as we know,

h i j k

Figure 2: For the tiles T = { abcde def efg hijk }
and a capacity C = 7, P3 = ({ abcde def }, { efg
hijk }) is a possible optimal pagination in n = 2
pages.

block: word . Moreover, in any collection of symbol sets (especially T , or a page), the separating
commas will be omitted: { May June July }.
Proposition 1. Pagination is NP-complete in
the strong sense.
Proof. Any given pagination P can be verified in
polynomial time. Furthermore, Bin Packing is a
special case of Pagination with no shared symbol. Hence, the latter is at least as difficult as the
former, which is strongly NP-complete.

In the rest of this paper, we focus on the associated NP-hard optimization problem (i.e., where
the aim is to minimize the number of pages).

1.3

Virtual machine allocation

Related works

Bin Packing and its numerous variants are among
the most studied optimization problems, and, as
such, regularly subjected to comprehensive surveys
[2, 3, 11, 15]. The purpose of the present section
is far more limited: to extract from this vast literature the few problems which exhibit the distinguishing feature of Pagination, i.e., which deal
with objects able to overlap in a non-additive fashion. For instance, despite its similar name, we
will not discuss Newspaper Pagination, a Bin
Packing variant studied in [14] for the placement
of (obviously non overlapping) blocks of text on the
columns of a generalized newspaper.
3

the general case has been left unexplored. In the
interest of differentiating it from these VM-oriented
models, we take the liberty to replace the terms
of VM packing, memory pages, VM and servers,
by the application-agnostic terms of Pagination,
symbols, tiles and pages (respectively).

given symbol across the pages. However, this leads
to another impasse:
Proposition 2. Minimizing the number of pages
and minimizing the number of symbol replications
are not equivalent.

counterexample. For C = 5, let T = { a1 357 a2
468 }. The optimal pagination {{ a1 357 }, { a2
468 }} minimizes the number of pages (2), but
Let us recall that a hypergraph G = (V, E) is not the number of replicas (symbol a is replicated
defined by a set of vertices V and a set of hyper- once). Conversely, the non-optimal pagination
edges E, where each element of E is a subset of V {{ a1 a2 }, { 357 }, { 468 }} minimizes the number
[1]. Bearing this in mind, it is easy to see the left- of symbol replications (0), but not the number of
hand part of Fig. 2 as a subset-based drawing [13] pages (3).
of a hypergraph mapping the instance, namely with
V = A (the set of vertices is the set of symbols) and
Therefore, contrary to appearances, Pagination
E = T ((the set of hyperedges is the set of tiles). has very little in common with Hypergraph ParSince Pagination is a partitioning problem, it is titioning3 .
natural to ask whether we could take advantage of
the extensive literature on Hypergraph PartiThe rest of this paper is organized as follows.
tioning. In [12] for instance, the latter problem In Section 2, we formulate Pagination as an inteis defined as “partitioning the vertices of a hyper- ger linear program (ILP), and introduce the various
graph into k roughly equal parts, such that a cer- metrics and rules used by our algorithms. Then, in
tain objective function defined over the hyperedges Section 3, we describe several heuristics and metais optimized”. Although our capacity constraint on heuristics for the problem. Finally, we compare
the symbols is reminiscent of this “roughly equal” the results produced by all the algorithms (exact
number of vertices, the main purpose of Pagina- or not) in Section 4, and conclude in Section 5.
tion is to partition the tiles (i.e., the hyperedges),
and certainly not the symbols (i.e., the vertices).
Theoretical tools
So, what happens if we try to exchange the roles 2
of the tiles and the symbols? This gives the following alternative hypergraph representation of the To look on our problem from another perspective,
instances of Pagination: V = T (the vertices are let us formulate it as an ILP problem. In addithe tiles) and E = A (the hyperedges are the sym- tion, we will be able to solve some (admittedly simbols). To be more specific, a symbol shared by ple) instances with a generic optimization software.
several tiles connects them as a hyperedge, while Thereafter, the introduction of several supplemena proper symbol (i.e., a symbol belonging to one tary concepts will permit us to actually generate
tile only) connects this tile to itself as a hyperloop. the instances, and to describe our own algorithms
Now, paginating G indeed amounts to partitioning for tackling the largest ones.
the vertices, but in the meantime two issues have
arisen. First, we do not care if each part contains 2.1 Integer
linear programming
roughly the same number of tiles: we want instead
model
that the number of involved hyperedges is at most
equal to C. Second, we have to express our objec- Numberings. We use the following sets of intive function (minimizing the number of pages) on dexes:
3 The problem studied in [6], and coincidentally named
the hyperedges (the symbols). To cite [12] again:
pagination
(by reference to the fixed-length contiguous block
“a commonly used objective function is to minimize
of virtual memory, or memory-pages), is in fact a special case
the number of hyperedges that span different par- of Hypergraph Partitioning, where the objective is to
titions”. At first sight, it would indeed seem rea- minimize the total weight of edge-cuts in a weighted graph,
sonable to minimize the number of replications of a with an upper bound on the size of the parts.
1.3.2

Hypergraph partitioning

4

• A = {i : i = 1, . . . , |A|} for the symbols;

symbol. Conversely, thanks to the objective function, every used page contains at least one symbol.
From Eq. 3, a page cannot contain more than C
symbols. Eq. 4 guarantees that, when a tile belongs
to a page, this page includes all its symbols5 . The
integrality constraints of the auxiliary variables of
Eq. 5 could be relaxed.

• T = {j : j = 1, . . . , |T |} for the tiles;
• P = {k : k ∈ N} for the pages4 .
Inputs.
• C is a strictly positive integer capacity;

• aij is an assignment of symbols to tiles: ∀i ∈ 2.2 Counting of the symbols
A, ∀j ∈ T, aij = 1 if i ∈ tj , and 0 otherwise.
Definition 2 (metrics). Let α be a symbol, t a tile
and p a set of tiles (most often, a page). Then:
Decision variables. For any i ∈ A, j ∈ T and
1. the size |t| of t is its number of symbols;
k ∈ P , we define:
2. the volume V(p) of p is its number of distinct
symbols: V(p) = | ∪t∈p t|; and its complement
C − V(p), the loss on p;

• xik as equal to 1 if symbol i is present on page
k, and 0 otherwise (pagination of the symbols);
• ykj as equal to 1 if tile j is present on page k,
and 0 otherwise (pagination of the tiles);

3. by contrast, the cardinality Card(p) is the
total number
P of symbols (distinct or not) in p:
Card(p) = t∈p |t|.

• zk as equal to 1 if page k is used, and 0 otherwise (unitary usage of the pages).

4. the multiplicity µp (α) counts the occurrences
of α in the tiles of p: µp (α) = |{t ∈ p : α ∈ t}|;

It is worth noting that xik = maxj∈T (aij ykj ) and
zk = maxj∈T (ykj ). The mathematical model of
Pagination is thus entirely specified with ykj : the
introduction of these auxiliary variables is only
used to achieve the linearity of its formulation.
Integer linear program.
lation of Pagination is:
X
min.
zk

5. the relative size of t on p is the sum of the
reciprocals of the
Pmultiplicities of the symbols
of t in p: |t|p = α∈t µp1(α) .
In recognition of the fact that a given symbol
may occur several times on the same page, the
terms cardinality and multiplicity are borrowed
from the multiset theory [21].

A possible ILP formu-

Example 2. In pagination P3 of Fig. 2: size |t1 | =
5, volume V(p1 ) = 6 (loss: 7 − 6), cardinality
Card(p1 ) = 5 + 3, multiplicity µp1 (e) = 2, relative
size |t2 |p1 = 1/2 + 1/2 + 1.

k∈P

s. t.

X

ykj

= 1,

∀j ∈ T (1)

k∈P

zk ≥ xik ,
X
xik ≤ zk C,

∀i ∈ A, ∀k ∈ P (2)

These definitions are extended to several pages
(i.e., sets of sets of tiles) by summing the involved
values:

∀k ∈ P (3)

i∈A

xik ≥ aij ykj ,

∀i ∈ A, ∀j ∈ T, ∀k ∈ P (4)

Example 3. In the same figure, volume V(P3 ) =
6 + 7 (loss: 7 − 1 + 7 − 7), cardinality Card(P3 ) =
Card(T ) = 5 + 3 + 3 + 4, multiplicity µP3 (e) =
Eq. 1 assigns each tile to exactly one page. Eq. 2
µT (e) = 2 + 1, relative size |t2 |P3 = |t2 |T = 1/2 +
ensures that a page is used as soon as it contains one
1/3 + 1/2.
xik , ykj , zk all binary, ∀i ∈ A, ∀j ∈ T, ∀k ∈ P (5)

4 For the sake of simplicity, we assume that an infinite
number of pages are available. In practice, prior to the calculations, this number will be limited to a reasonable value,
either given by a heuristic, or |T | (one tile per page) in the
worst case.

5 Although Eq. 4 produces a lot of unnecessary constraints of the form xik ≥ 0, we prefer it to the equivalent,
but slightly less explicit formulation xik ≥ ykj , ∀j ∈ T, ∀i ∈
tj , ∀k ∈ P .

5

We are now able to express a first interesting
difference with Bin Packing:

In other words, the tile sets we deal with are
Sperner families [20]. It follows that:

Proposition 3. A pagination whose loss is mini- Corollary 1 (Sperner’s Theorem).
 A page of caC
pacity
C
contains
at
most
mal is not necessarily optimal.
bC/2c tiles.
Rule 2. No tile contains all the symbols: @t ∈ T :
t = A.

counterexample. For C = 4, the tile set T = { 12
13 23 ab ac bc } has a loss of 1+1 on the optimal
pagination ({ 12 13 23 }, { ab ac bc }); but a loss
of 0 + 0 + 0 on the non-optimal pagination ({ 12
ab }, { 13 ac }, { 23 bc }).

Proof. Direct consequence of Rule 1.
Rule 3. Each tile has less than C symbols: ∀t ∈
T , |t| < C.

As seen in this counterexample, for the complete
page set, multiplicity, cardinality and relative size
do not depend on the pagination. Then:

Proof. Let t be an arbitrary tile. If |t| > C, the
problem has no solution. If |t| = C, then no other
tile t0 could appear on the same page as t without
violating Rule 1. Let P 0 be an optimal pagination
of the reduced instance T \{t}. Then P = P 0 ∪{{t}}
is an optimal pagination of T .

Proposition 4. A pagination is optimal if and
only if the average cardinality of its pages is maximal.

Proof. Since thePsum of the page cardinalities is Rule 4. No symbol is shared by all tiles: @α ∈ A :
always equal to t∈T |t|, its average depends only ∀t ∈ T , α ∈ t.
of the size n of the pagination. Hence, minimizing
Proof. Otherwise, let P 0 be an optimal pagination,
this size or that average is equivalent.
for a capacity of C − 1, of the reduced instance
T 0 = {t \ α : t ∈ T and t 6= {α}}. Then adding α
2.3 Simplifying assumptions
to each page of P 0 gives an optimal pagination P
Definition 1 encompasses many instances whose of T for capacity C. Should a tile {α} exist in T ,
pagination is either infeasible (e.g., one tile exceeds it can be put back at no cost on any page of P.
the capacity), trivial (e.g., all tiles can fit in one
page) or reducible (e.g., one tile is a subset of another one). The purpose of this subsection is to
bring us closer to the core of the problem, by ruling out as many such degenerated cases as possible.
For each one, we prove that there is nothing lost for
an offline algorithm to ignore the corresponding instances.

In other words, T has not the Helly property [5].
Contrast this with VM Packing [19], where the
mere existence of root symbols violates this rule.
Rule 5. Each symbol belongs to at least one tile:
∀α ∈ A, ∃t ∈ T : α ∈ t.
Proof. By Definition 1 of an instance.
Rule 6. Each tile is compatible with at least another one: ∀t ∈ T , ∃t0 ∈ T \ {t} : |t ∪ t0 | ≤ C.

Rule 1. No tile is included in another one:
∀(t, t0 ) ∈ T 2 : t 6= t0 , t 6⊆ t0 .

Proof. If there exists a tile t not compatible with
Proof. If t ⊆ t0 , then t and t0 can be put together
any other, any solution should devote a complete
on the same page of the optimal solution.
page to t. The conclusion of the proof of Rule 3
Remark 1. This does not hold for an online algo- still applies here.
rithm. Take for instance T = { 12 345 126 378 }
and C = 5. If the tiles are presented in this order,
the first two may be placed on the first page, making necessary to create a new page for each remaining tile: {{ 12 345 }, { 126 }, { 378 }}. An optimal
pagination would require two pages only: {{ 12
126 }, { 346 378 }}.

Rule 7. C > 2.
Proof. Since all tiles contain at least one symbol,
Rule 3 implies C ≥ 2. Assume that C = 2,
i.e., all tiles consist in one single symbol. Hence,
{{t1 , t2 }, {t3 , t4 }, ...} is an optimal pagination of T
in d |T2 | e pages.
6

Rule 8. C < |A|.

• First Fit rescans sequentially the pages already created, and puts the new tile in the
first page where it fits.

Proof. Otherwise, all tiles could fit in one page.

• Best Fit always chooses the fullest page, i.e.,
the page with maximal volume. Such a criterion needs to be clarified in our generalization
of Bin Packing: fullest before or after having
put the new tile? This alternative should give
rise to two variants.

To sum up, an optimal solution of an instance violating Rules 1, 3 (with |t| = C), 4, 5 or 6, could be
deduced from an optimal solution of this instance
deprived of the offending tiles or symbols; an instance violating Rule 3 (with |t| > C) would be infeasible; an instance violating Rules 2, 7 or 8 would
be trivial. All these rules can be tested in polynomial time, and are actually required by our instance
generator (Section 4.1).

3

• Worst Fit, contrary to Best Fit, favors the
less full page.
• Almost Worst Fit is a variant of Worst
Fit opting for the second less full page.

Heuristics

These algorithms are known under the collective
name of Any Fit (AF). In their offline version, presorting the items by size has a positive impact on
their packing; but for Pagination, such a sorting
criterion would obviously be defective: due to possible merges, a large tile often occupies less volume
than a small one.

In this section, we investigate four families of
heuristics for Pagination, from the simplest to
the most sophisticated one. The first family consists of direct adaptations of the well-studied Bin
Packing’s greedy Any Fit algorithms; we show
that, in Pagination, their approximation factor
cannot be bounded. The second family is similar,
but relies on the overlapping property specific to
our problem; a general instance is devised, which
shows that the approximation factor of their offline
version is at least 3. With the third algorithm, we
leave the realm of greedy decisions for a slightly
more complex, but hopefully more efficient strategy, based upon a reentering queue. Finally, we
present two genetic algorithms and discuss which
encoding and cost function are better suitable to
Pagination. All of this is carried out from a theoretical perspective, the next section being devoted
to the presentation of our benchmarks.

3.1.2

A general unfavorable case

Regardless of its scheduling (online or offline), no
AF algorithm has performance guarantee on the
following extensible Pagination instance.
Let C be an even capacity (C = 4 on Fig. 3).
Let Aα = {α1 , ..., αC } and Aβ = {β1 , ..., βC } be
two sets of distinct symbols such that A is the
 disAα
joint union of Aα and Aβ . Let Tα = C/2
and
Aβ 
C
Tβ = C/2 be the set of the 2 -combinations of Aα
and Aβ (respectively). Then Popt = {Tα , Tβ } is an
optimal pagination of T = Tα ∪ Tβ in 2 pages.
Now, let us feed these tiles to any of our AF
algorithms, but only after having sorted them in the
3.1 Greedy heuristics inspired from worst order: since all of our tiles have the same size
C/2, we are indeed free to organize them the way
Bin Packing
we want. The most unfavorable schedule simply
3.1.1 Definitions
involves alternating the tiles of Tα and Tβ . In this
The question naturally arises of how the Bin Pack- way, regardless of the selected AF algorithm, the
ing classical approximation algorithms [2] behave first two tiles would saturate the first page, the next
in the more general case of Pagination. Let us two, the second page, and so on. In total, an AF
algorithm
would then create n = |Tα | = |Tβ | =
enumerate a few of them with our terminology:

C
C!
C/2 = (C/2)!2 pages instead of 2. In this family,
• Next Fit simply stores each new tile in the the approximation factor is thus unbounded. This
last created page or, should it exceed the ca- stands in stark contrast to the efficiency of the AF
algorithms on Bin Packing—where, for instance,
pacity, in a newly created page.
7

α1

α2
α2

α3

β1
β3

α2
α4
β3

α3

α1
α3

α4

α1

β1

α2

β2

α3

β3

α4

β4

α1

α2

α3

α4

β1

β2

β3

β4

α1
β2

β1

β2

α4

β4

online version, since the new tile is given, this optimization relies only on the past assignments.
α1

α2

α3

α4

β1

β2

β3

β4

3.2.2

A general unfavorable case

Before introducing the particular heuristic we have
the most thoroughly tested, Best Fusion, let us
α3
β4 α4
β1
β2
β3
mark out the limitations of the algorithms of this
family. We will design an extensible instance whose

all tiles are equivalent with respect to these metrics.
Figure 3: To the left, a set T = Tα ∪ Tβ of 2 42 =
As such, they may be taken in any order, including
12 tiles; at the center, a pagination of capacity 4
the worst, which ensures that the reasoning is valid
calculated by the Any Fit algorithms when the tiles
for both online and offline scheduling.
of Tα and Tβ are fed alternatively; to the right, an
Take an even capacity C, and A0 = {α1 , ..., αC }
optimal pagination.
A0
a first subset of A. Let T0 = C−1
the (C − 1)combinations of A0 , which amount to C tiles of
First Fit was recently shown [4] to achieve an size C − 1. From now on, to better understand the
general construction, we will illustrate each step on
absolute factor of exactly 1.7.
an example with C = 4:
β3

3.1.3

β4

β4

α2

β2

β1 α1

Study case: First Fit algorithm

A0 = 1234 ,

For our tests, we have chosen to focus on First Fit
(in its online version). The worst case complexity
can be analyzed as follows. There are |T | tiles to
paginate. At worst, according to Rule 6, there exists only one tile compatible with any other, resulting in |T | − 1 pages. Lastly, each set intersection
costs a linear time in the size of the candidate tile.
Hence, the overall complexity is O(|T |2 Card(T )).
Note that in Bin Packing, for n items, an appropriate data structure can reduce the straightforward quadratic complexity to O(n log(n)) [11].
This optimization is not applicable here, where the
current volume of a given page says little about its
ability to accommodate a given tile.

3.2
3.2.1

T0 = { 123 124 134 234 }

Introduce two more symbols, namely a and b, which
will be used to lock the pages. Partition T into C2
couples of tiles: (t1 , t2 ), (t3 , t4 ), ..., (tC−1 , tC ). From
each such couple, form Ai = (t2i−1 ∩ t2i ) ∪ {a, b}
with 1 ≤ i ≤ C2 , a subset of A. In the same way as

Ai
on A0 , define Ti = C−1
on each Ai :
A1 = 12ab ,

T1 = { 12a 12b 1ab 2ab }

A2 = 34ab ,

T2 = { 34a 34b 3ab 4ab }

Constructing this instance is actually constructing
an optimal solution to it. Indeed, for the whole tile
set, |Popt | = C2 + 1:

Specialized greedy heuristics

p1 = { 123 124 134 234 } → 1234
p2 = { 12a 12b 1ab 2ab } → 12ab

Definition

p3 = { 34a 34b 3ab 4ab } → 34ab

We can easily improve on the Bin Packing heuristics by taking into account the merging property of
Pagination items.
The corresponding offline greedy algorithms always select, among the remaining tiles, the one
which minimizes or maximizes a certain combination of the metrics introduced in Definition 2 (e.g.,
volume, multiplicity, relative size, etc.). In their

Now, let us construct a non-optimal pagination.
This is done by pairing each tile of T0 with a tile
including a “locking” symbol. Specifically, on pages
2i − 1 and 2i, put respectively t2i−1 and t2i , and
lock these pages with tiles (t2i−1 ∩ t2i ) ∪ {a} and
(t2i−1 ∩ t2i ) ∪ {b} (respectively) from Ti . This pro8

cess creates C locked pages:

page is locked in a bad state. In practice, this flaw
is easily fixed by the so-called decantation posttreatment (see Section 3.5), which can be considered as a multi-scale First Fit6 .

p01 = { 123 12a } → 123a
p02 = { 124 12b } → 124b
p03 = { 134 34a } → 134a

3.3

p04 = { 234 34b } → 234b

The following non-greedy approach has the ability
to reconsider past choices whenever better opportunities arise. As a result, in particular, it always
finds the optimal solution of the unfavorable cases
outlined in Sections 3.1.2 and 3.2.2.
The main idea is to add a given tile t to the page
p on which t has the minimal relative size, even if
this addition actually overloads p. In this case, the
algorithm immediately tries to unload p by removsize
ing the tile(s) t0 of strictly smallest relative
size ratio.
The removed tiles are rescheduled at the latest by
adding them to a FIFO data structure, and simultaneously forbidden to reenter the same page—this
ensures termination. When the main loop is over,
the possible remaining overloaded pages are suppressed, and their tiles redistributed by First Fit.

But what enables us to construct such inefficient
two-tile pages? All tiles having the same size, it is
clear that the first one can be chosen arbitrarily.
Now, let t0 be an eligible second tile, and p0 the
resulting page. Then, all t0 are equivalent under our
various metrics: same size |t0 | = C −1, same volume
V(p0 ) = C, same cardinality Card(p0 ) = 2(C − 1),
C
same relative size |t0 |p0 = C−2
2 +1 = 2 . So, nothing
prevents our greedy algorithms to systematically
select the worst candidate.
If C > 2, the C − 2 tiles including both a and b
still remain in every tile set (but T0 ). For each one,
gather its tiles on a new page:
p05 = { 1ab 2ab } → 12ab
p06 = { 3ab 4ab } → 34ab

Algorithm: Overload-and-Remove

Finally, we have obtained a non-optimal pagination
P totaling C + C2 = 3C
2 pages. Hence, for a given
even capacity C, any greedy algorithm of this fam3C
ily may yield |P|P|
= C+2
times more pages than
opt |
the optimal. In other words, its approximation factor is at least 3.
3.2.3

Overload-and-Remove heuristic

Q ← queue containing all the tiles of T
P ← pagination consisting of one empty page
while Q is nonempty:
| t ← dequeue(Q)
| Pt ← pages of P where t has never been put on
| if Pt has no page p such that |t|p < |t|:
| | add to P a new page consisting solely of {t}
| | continue with next iteration
| p ← page p of Pt such that |t|p is minimal
| put tile t on page p
| while V(p) > C and ∃t1 , t2 ∈ p2 : |t|t11||p 6= |t|t22||p :
| | remove from p one tile t0 minimizing |t0 |/|t0 |p
| | enqueue(Q, t0 )
remove all the overloaded pages from P
put their tiles back in P (by First Fit)

Study case: Best Fusion algorithm

In our benchmarks, the following criterion was
used: for each tile t, let p be the eligible page on
which the relative size |t|p is minimal. If |t|p < |t|,
then put t on p; otherwise, put t on a new page.
We call Best Fusion the online version of this algorithm. Its worst-case complexity is the same as
in First Fit, i.e., O(|T |2 Card(T )).
Since a new page is created for every tile whose
assignment to an existing page would bring no immediate benefit, the cases raised in Section 3.1.2
are solved to optimality. However, the downside
of such a strategy becomes readily apparent with
pure Bin Packing instances: in the absence of
shared symbols, each new tile will trigger the creation of a new page. Consequently, Best Fusion
has no more performance guarantee than the AF
algorithms. The difference here is that no resulting

In the worst case, a given tile might successively
overload and be removed from all pages, whose to6 Strictly speaking, with this post-treatment, Best Fusion is no more greedy. Preserving at the same time the
greediness of the algorithms of the present family, and an
acceptable behavior on both Section 3.1.2’s and pure Bin
Packing’s instances, can nevertheless be attained by means
of offline scheduling (described in Section 3.2.1). This is at
least |T | times more complex, and still untested.

9

tal number is at most |T |. Each trial requires one Mutation. It consists in transferring one ranset intersection on each page. Hence, the overall domly selected tile from one page to another.
complexity is O(|T |3 Card(T )).

3.4
3.4.1

Crossover. The standard two-point crossover
applies here without requiring any repair process.

Genetic algorithms
Standard model

3.4.2 Grouping model
Encoding. Any pagination (valid or not) on n
pages is encoded as a tuple (k1 , ..., k|T | ) where kj ∈ In [7], Falkenauer et al. show that classic GAs are
[1, n] is the index of the page containing the tile tj . not suitable to the grouping problems, namely
Example 4. The four paginations of Fig. 2 would “optimization problems where the aim is to group
be respectively encoded as (1, 2, 3, 4), (1, 2, 2, 3), members of a set into a small number of families, in
order to optimize a cost function, while complying
(1, 1, 2, 2) and (1, 1, 1, 2).
with some hard constraints”. To take into account
Due to its overly broad encoding capabilities,
the structural properties of such problems, the auStandard GA is not guaranteed to produce a
thors introduce the so-called grouping genetic
valid pagination. Our fitness function is devised
algorithms (GGA). Their main idea is to encode
with this in mind, in such a way that an invalid
each chromosome on a one gene for one group basis.
chromosome would always cost more than a valid
The length of these chromosomes is thus variable:
one. Thus, seeding the initial population with at
it depends on the number of groups. Crucially, the
least one valid individual will be enough to ensure
belonging of several items to the same group is prosuccess.
tected during crossovers: the good schemata are
more likely to be transmitted to the next generaEvaluation. Our aim is twofold. First and fore- tions.
most, to penalize the invalid paginations; second,
Pagination is clearly a grouping problem, moreto reduce the volume of the last nonempty page.
over directly derived from Bin Packing—one of
For this purpose, we will minimize the fitness functhe very problems Falkenauer chooses to illustrate
tion f defined as follows:
his meta-heuristic. We thus will adapt, and someas one page is overloaded (i.e., ∃k ∈ P :
PAs soon
times directly apply his modelization.
i
i∈A xk > C), we count |T |C symbols (as if all
possible pages were saturated), to which we also
Encoding. A valid pagination on n pages is enadd every extra symbol:
coded as a tuple (p1 , ..., pn ) where pk is the set of
X
X

f (P) = |T |C +
max 0, (
xik ) − C
(6a) the indexes of the tiles put on the k th page.
k∈P

i∈A

Otherwise, let us call k the index of the last
nonempty page (i.e., such that ∀k 0 > k, zk0 = 0).
Count (k − 1)C symbols (as if all nonempty pages
but the last one were saturated), and add the number of symbols on page pk :
X
f (P) = (k − 1)C +
xik
(6b)

Example 6. This time, the paginations of Fig. 2
would be encoded as ({1}, {2}, {3}, {4}), ({1},
{2, 3}, {4}), ({1, 2}, {3, 4}) and ({1, 2, 3}, {4}) (respectively). Or, in Falkenauer’s indirect, but sequential notation: 1234:1234, 1223:123, 1122:12
and 1112:12, where the left part denotes, for each
j th tile, the index of its page; and the right part,
the list of all pages.

i∈A

Evaluation. In our notation, the maximization
function of [7] forP
Bin Packing would be expressed
n
as fBP (P) = n1 k=1 ( C1 V(pk ))d . In other words,
the average of volume rates raised to a certain disparity d, which sets the preference given to the
bins’ imbalance: thus, for the same number of bins

Example 5. If all tiles of Fig. 2 were put on a single (invalid) page, by (6a), the fitness value would
reach 4 × 7 + 4 = 32. By (6b), the paginations
P1 to P4 have a fitness value of 3 × 7 + 4 = 25,
2 × 7 + 4 = 18, 1 × 7 + 7 = 14, and 1 × 7 + 4 = 11
(respectively).
10

and the same total loss, the greater the disparity,
the greater the value of an unbalanced packing.
Although this formula still makes sense in the
context of Pagination, we should not apply it as
is. Indeed, whereas minimizing the loss amounts
to minimizing the number of bins, Proposition 3
warns us this is actually untrue for the number
of pages: in the associated counterexample, with
d = 2 (the empirical value proposed by [7]), the optimal pagination would be evaluated to ((3/4)2 +
(3/4)2 )/2 = 0.5625, and the suboptimal one to
((4/4)2 + (4/4)2 + (4/4)2 )/3 = 1.
Instead of privileging the high volume pages, we
will privilege the high multiplicity ones (i.e., replace
V(pk ) by Card(pk )). Proposition 4 guarantees that
the higher the average page multiplicity, the better
the overall pagination.
One detail remains to be settled: ensure that
the quantity raised to the power d never exceeds
1. Here, in the same way that V(pk ) is bounded
by C, Card(pk ) is bounded by Card(T ), and even,
more tightly, by the sum of the multiplicities of the
C most common symbols, which we will note MCT .
This leads us to the following fitness function for
Pagination:

3.5

Post-treatment by decantation

We introduce here a quadratic algorithm which, in
an attempt to reduce the number of pages, will be
systematically applied to the results produced by
all our heuristics but First Fit. Its three steps
consist in settling at the beginning of the pagination as much pages, components and tiles as possible. First, we must specify what is a component:
Definition 3. Two tiles are connected if and only
if they share at least one symbol or are both connected to the same intermediate tile. The (connected) components are the classes of the associated equivalence relation.
Example 8. In Fig. 2, the components of the instance are { abcde def efg } and { hijk }.

n

1 X  Card(pk ) d
f (P) =
n
MCT

Crossover. The two parents (possibly of different length) are first sliced into three segments:
(a1 , a2 , a3 ) et (b1 , b2 , b3 ). The tiles of b2 are withdrawn from a1 and a3 : a01 = a1 \b2 and a03 = a3 \b2 .
To construct the first offspring, we concatenate
(a01 , b2 , a03 ), sort the missing tiles in decreasing order, and insert then back by First Fit. The second offspring is calculated in the same manner (just
exchange the roles of a and b).

(7)

Definition 4. A valid pagination is said to be decanted on the pages (resp., components, tiles) if
Example 7. In Fig. 2, MCT = 3 + 2 + 2 + 1 + 1 + and only if no page contents (resp., component,
1 + 1 = 11. With d = 2, the four paginations are tile) can be moved to a page of lesser index without
respectively evaluated as follows:
making the pagination invalid.

(5/11)2 + (3/11)2 + (3/11)2 + (4/11)2 /4 ' 0.12 Example 9. In Fig. 2, P3 is decanted on the pages,
but not on the components or the tiles. P4 is a fully

(5/11)2 + (6/11)2 + (4/11)2 /3 ' 0.21 decanted pagination (on the pages, the components

(8/11)2 + (7/11)2 /2 ' 0.47 and the tiles).

(11/11)2 + (4/11)2 /2 ' 0.57
Obviously, a pagination decanted on the tiles is
decanted on the components; and a pagination deAs one can see, P4 (the most unbalanced pagina- canted on the components is decanted on the pages.
tion) scores better than P3 . The difference would To avoid any unnecessary repetition, the correincrease with disparity d.
sponding operations must then be carried out in
the reverse direction. Moreover, the best decantation of a given pagination P is attained by decantMutation. The mutation operator of [7] consists
ing P successively on the pages, the components,
in emptying at random a few bins, shuffling their
and then the tiles.
items, and then inserting them back by First Fit.
We follow the exact same procedure, but without Example 10. Let ({ 123 }, { 14 567 }, { 189 }) be a
the suggested improvements: at least three rein- pagination in 3 pages with C = 5. Its decantation
on the components, ({ 123 14 }, { 567 }, { 189 }),
serted bins, among which the emptiest one.
k=1

11

does not decrease the number of pages, as opposed to its decantation on the pages: ({ 123 189 },
{ 14 567 }). For an example on components/tiles,
let us substitute 567 with 1567 in the instance.
Let ({ 123 }, { 14 1567 }, { 189 }) be a pagination in
3 pages with C = 5. Its decantation on the tiles,
({ 123 14 }, { 1567 }, { 189 }), does not decrease the
number of pages, as opposed to its decantation on
the components: ({ 123 189 }, { 14 1567 }).
This decantation algorithm is thus implemented
as a sequence of three First Fit procedures of decreasing granularity. In our tests, the interest of
such a post-treatment varies greatly: it is of course
useless on First Fit, but reduces the outcomes
of GAs by one page in about 0.1 % of cases, and
both Best Fusion and Overload-and-Remove
by up to ten pages for about 21 % and 40 % of
instances, respectively.

4

Since the latter behavior requires both a specially
constructed instance and a particularly weak pagination algorithm, we have chosen to add this constraint during the generation of our random test
sets: in practice, it will have no other effect than
to avoid polluting the instances with a bunch of
unmergeable, interchangeable, easy-to-place tiles.
Our instance generator takes as input a capacity
C, a number |A| of symbols and a number |T | of
tiles. It follows a three-step process:
1. Calculate a standard deviation s = C5 and a
mean m = RC
4 , where R is a random variable
uniformly distributed on {1, 2, 3}.

Experimental results

Supplementary material. In order to empower
the interested readers to reproduce our analysis and
conduct their own investigation, we provide at [9]
a ∼60 MB Git repository containing: the whole
set of our random instances (gauss); a companion
Jupyter Notebook (analysis.ipynb) which generates every plot and numerical result mentioned or
alluded in the present section; some instructions for
using this notebook interactively (README.md).

4.1

all pages are saturated, P 0 ∪ {{t}} is not necessarily an optimal pagination of T . Take for instance
T = { 0 123 45 167 89 } and C = 5. The reduced instance T \ { 0 } admits an optimal pagination P 0 = {{ 123 45 }, { 167 89 }}, all of whose
pages are saturated. Nevertheless, the pagination
P 0 ∪ {{ 0 }} has one page more than the optimal
pagination P = {{ 123 167 }, { 45 89 0 }}.

2. Draw an integer k from the corresponding normal distribution: k ∼ N (m, s2 ). If 1 < k < C
(Rules 3 and 9), make a candidate tile up from
a uniform random sample of k distinct symbols. Add it to the accepted set if and only if
Rule 1 is still satisfied. Repeat this step until
|T | tiles are obtained.
3. Accept the resulting instance if and only if
Rules 4, 5 and 6 are satisfied.

Generating a test set

This algorithm has been called repeatedly with C
First, let us introduce another simplifying assump- varying from 15 to 50 in steps of 5, |A| varying
tion:
from C + 5 to 100 in steps of 5 (for lesser values, by
Rule 7, all symbols would fit in a single page) and
Rule 9 (optional). All tiles contain more than one
|T | varying from 20 to 100 in steps of 5. Although
symbol: ∀t ∈ T , |t| > 1.
in some rare cases, numerous passes were required
This rule cannot be considered on the same level before halting on a result, it proved to be robust
than those of Section 2.3: forbidding one-symbol enough to produce, for each distinct combination
tiles may theoretically make some instances easier of its parameters, six valid instances (for a total of
10,986 instances).
to paginate.
counterexample. By definition, no tile is empty. 4.2 Measuring the statistical diffiSuppose there exists a tile t of size 1, and let P 0
culty of a given instance
be an optimal pagination of the reduced instance
T \ {t}. If there exists a page p0 ∈ P 0 such that What is a difficult instance of Pagination? Al|p0 | < C, then adding t on p0 produces an optimal though we cannot answer this question in all generpagination of T . However, in the rare cases where ality, the highly experimental nature of the present
12

approach certainly enables some observations to be
made. Indeed, we have not only generated several
thousands of instances, but also submitted them to
no less than six different solvers: one ILP, two genetic algorithms, two greedy algorithms, and one
specialized heuristic (not counting its sorted variant), Overload-and-Remove. When these various methods all produce roughly the same number
of pages, one can conclude that the instance was
an easy one; conversely, when the pagination size
differs greatly among methods, it clearly presents
some particular challenges.
The dispersion of the pagination sizes can be
measured in several ways: range (i.e., difference
between minimum and maximum), average range
(i.e., average difference with the minimum), standard deviation, median absolute deviation... Although, statistically speaking, the last one is the
most robust, the second one proved to be slightly
more suited to our problem, where outliers are arguably no accidents, but rather evidences of some
significant structural features. Hence:

that, when the optimum is known, the same number of pages is produced by at least one heuristic
in 1 − 4/43 = 91 % of the cases.
Finally, as its name suggests, this measure depends on our set of algorithms. Therefore, adding
another one may either increase or decrease the statistical difficulty of any instance. Of course, the
more “reasonable” algorithms would be tested, the
less the prevalence of this effect.

4.3

Predicting the statistical difficulty of a given instance

Pagination can be seen as an almost continuous
extension of Bin Packing: being given a pure Bin
Packing instance (i.e., no tile has shared symbols),
we may gradually increase its intricacy by transforming it into a Pagination instance as convoluted as desired (i.e., many tiles share many symbols). Therefore, we can expect that:

There are some caveats. First, this measure of
the statistical difficulty is intrinsically correlated
(Pearson’s r = 0.792 [16]) to the size of the best
pagination (e.g., if the best algorithm produces 2
pages, it is unlikely that any of its competitors will
produce 20 pages). This is by design. Intuitively,
a “large” random instance is more difficult to paginate than a “small” one. For example, the larger
an instance, the longer it takes for a brute force
algorithm to find the optimum. In our tests, normalizing the difference by dividing it by the best
size has indeed proven counterproductive.
Second caveat, this measure only makes sense
for random instances. We certainly could devise a
particular instance which would be easy for a special tailored algorithm, but difficult for our generalpurpose solvers.
Third caveat, CPLEX gave us the optimal pagination for only 43 instances. That the minimum
heuristic result is the optimum, or a tight estimate, is therefore not guaranteed. Note however
13

Average range (statistical difficulty)

Conjecture 2. The statistical difficulty of a given
random instance is strongly correlated to the denConjecture 1. The statistical difficulty of a sity of its shared symbols, or average multiplicgiven instance can be approximated by the differ- ity.
ence between the average and the minimal number
of pages in the paginations calculated by our various
8
solvers.
6
4
2
0
0

10

20

30

40

Average multiplicity

50

60

70

Figure 4: Statistical difficulty by average multiplicity (r = 0.784). A multiplicity of 10 indicates that,
in the corresponding instances, a given symbol is
shared by an average of 10 tiles. For these instances, the average range of pagination sizes produced by our different solvers (the so-called difficulty) varies between 0 (all solvers obtain the same
number of pages) and 5.

Figure 4 tests this hypothesis on our instance set:
the average multiplicity of a given random instance
appears to be a good predictor (r = 0.784) of its

statistical difficulty. Is it the best one? We can [9] for these exact values). Overall, more than half
think of a few other possible candidates, and calcu- of them concentrate between multiplicities 2 and 9.
late their correlation with the statistical difficulty: Thus, any observation made on the higher multiplicities (and the smaller ones) must be approached
• r = −0.082 for |A|, the number of symbols;
with great caution.
• r = 0.366 for |A|×|T |, the size of the instance,
i.e., the number of bits required to encode it. 4.4 Discussion
More precisely, a stream of |A|×|T | bits, where
the ith bit is 1 if and only if the bi/|T |c-th tile 4.4.1 Behavior of the integer linear program
of T includes the (i mod |T |)-th symbol of A
(plus three long integers for the capacity, the As seen in Fig. 5, only a limited subset of our
size of the alphabet and the number of tiles, all instances (342 of 10,986) have been submitted to
of them being dominated by the first quantity). CPLEX. This was for practical reasons: despite a
• r = 0.563 for |T |, the number of tiles.
• r = 0.770 for Card(T ), the sum of the tile
sizes.

10 3

All instances
Submitted to CPLEX
Solved to optimality by CPLEX

4.4.2

Comparison of the heuristic methods

Execution time (seconds, log scale)

10 2
10 1

10 0
0

(1, 3]
(3, 5]
(5, 7]
(7, 9]
(9, 11]
(11, 13]
(13, 15]
(15, 17]
(17, 19]
(19, 21]
(21, 23]
(23, 25]
(25, 27]
(27, 29]
(29, 31]
(31, 33]
(33, 35]
(35, 37]
(37, 39]
(39, 41]
(41, 43]
(43, 45]
(45, 47]
(47, 49]
(49, 51]
(51, 53]
(53, 55]
(55, 57]
(57, 59]
(59, 61]
(61, 63]
(63, 65]
(65, 67]

Number of instances (sym-log scale)

Among these candidates, Card(T ), the cardinality
of the tile set, is almost as good a predictor as
Card(T )/|A|, its average multiplicity. The choice
of the latter value is mainly dictated by the fact
that it involves the number of symbols. Indeed,
when |A| approaches Card(T ), Pagination approaches Bin Packing, which we expect to reduce
the difficulty of the instance.

powerful testing environment (Linux Ubuntu 12.04
on Intel Core i5-3570K with 4 cores of 3.4 GHz and
4 GB of RAM), CPLEX turned out to need a generous time-limit of one hour to be able to solve to
optimality a mere 12.6 % of this subset (i.e., 43
instances). The ratio dropped to 3.8 % when the
average multiplicity reached 13; above 20, no more
success was recorded. Thus, this ILP quickly becomes irrelevant as the multiplicity increases, i.e.,
as Pagination starts to distinguish itself from Bin
Packing.
Unless we could find strong valid inequalities to
improve it, our experimentations suggest that the
heuristic approach constitutes a better alternative.

Ranges of average multiplicity

10 3
10 2
10 1
10 0
10 -1
10 -2

10

20

30

40

Average multiplicity (rolling mean on 150 instances)

Figure 5: Number of instances by average multiplicity (sym-log scale).

50

Figure 6: Performance of the main heuristics (log
scale). From top (slowest) to bottom (fastest):
Grouping GA, Standard GA, Overload-andRemove, Best Fusion, First Fit.

Before we go any further, it is important to be
aware that the average multiplicities in our test set
are far from being evenly distributed (Fig. 5): for
example, there are 1119 instances whose average
multiplicity lies between 4 and 5, but only 107 between 23 and 24, and 10 between 53 and 54 (see

All of our heuristics have been implemented in
Python 2.7, and tested under Mac OS X 10.10 on
14

Average pagination size vs. best known result

Intel Core i5-3667U with 2 cores7 of 1.7 GHz and
4 GB RAM. The average execution time ranges
from less than 0.1 seconds for the greedy algorithms, 1 second for Overload-and-Remove, 7
seconds for Standard GA, through 90 seconds
for Grouping GA. For the two GAs, the following parameters were selected as offering the best
ratio quality/time: 80 individuals, 50 generations,
crossover rate of 0.90, mutation rate of 0.01. Their
initial population was constituted of valid paginations obtained by applying First Fit to random
permutations of the tile set. Figure 6 shows how
the various algorithms scale as multiplicity grows:
performance-wise at least, all remain practical on
our most difficult instances.
Note that this analysis, and the next one, are
carried out on a moving window of equally-sized
subsets of instances sorted by increasing average
multiplicity: by eliminating noise, this technique
helps to visually separate the different curves; it has
the side-effect of making some endpoints disappear,
but, as explained in Section 4.3, their loss is greatly
outweighed by the gain of a constant confidence
level on the remaining data.
1.00
0.95
0.90

Grouping GA
Standard GA
Overload-and-Remove
Best Fusion
First Fit

heuristics. The irregularities of the top line also
somehow give indirect insight into the rare achievements of our ILP (among the 342 instances submitted to CPLEX, only 6 proved to have a better
solution than the result of the best heuristic). General observations and recommendations that can be
derived from the underlying data are as follows.
Standard GA can definitely be ruled out.
As expected from Section 3.4.2, Standard GA
was consistently surpassed by the more sensible Grouping GA: no more than 4 exceptions
(0.036 %) occurred. Rather suspiciously, all of
them involved a minimal instance, i.e., subject to
a 2-page pagination. Further examination revealed
that, in each case, this optimal pagination was already present in the initial random population constructed by First Fit; hence, its apparition was
by no means indicative of some rare small-scale superiority of Standard GA: due to the fact that
our implementation systematically transmits the
best individual to the next generation, it was preserved, rather than produced by the evolution. This
may also partially explain as pure chance the comparatively good performances in the lowest multiplicities; beyond that, the curve stabilizes quickly
around an 85 % efficiency of Grouping GA. Finally, note that, up to an average multiplicity of 15,
Standard GA is even outclassed by Overloadand-Remove, a six times faster heuristic.

0.85

Grouping GA produces the best overall results. When quality is the top priority, Group0.80
ing GA is the way to go: it almost always (99.64 %
of cases) guarantees equivalent or smaller pagina0.75
tions than any other heuristic. ILP did improved on
10
20
30
40
50
it in 6 cases (1.75 % of the 342 selected instances):
Average multiplicity (rolling mean on 150 instances)
2 with a better feasible solution, 4 with the opFigure 7: Relative quality of the five main heuris- timal solution. But even if such good surprises
size
would multiply on the whole set of instances, we
tics. The outcomes are plotted at y = best
size ,
with y = 1 corresponding to the best known solu- must keep in mind that CPLEX was given one hour
tion (which is either the optimal or the best feasible on four cores, against about 90 seconds to a pure
solution found by CPLEX, or the smallest approx- Python implementation running on a single core
(twice as slow): Grouping GA has yet to unleash
imation calculated for the given instance).
its full potential.
Figure 7 compares the results of the various

The fastest non-genetic contender is
Python can only execute on a single core, we usu- among Best Fusion and Overloadally launched two processes in parallel.
and-Remove. If speed matters, the choice
7 Since

15

depends on the average multiplicity of the instance: in most cases, Overload-and-Remove
records quite honorable results. It is even the only
non-genetic algorithm which proved occasionally
(0.2 % of cases) able to beat Grouping GA.
However, its quality regularly deteriorates (count
up to 5 % for a 10 points increase in multiplicity).
Around 35, somewhat surprisingly, the greedy
algorithms get more and more competitive, with
Best Fusion taking over at 40.
Regardless
of why this happens, a specialized heuristic for
such deeply intricate instances would certainly be
needed; in the meantime, Best Fusion represents
the best tradeoff when average multiplicity meets
or exceeds the 40 mark.

5

Conclusion

In this paper, we revisited an extension of Bin
Packing originally devised by Sindelar et al. [19]
for the virtual-machine colocation problem. We
broadened its scope to an application-agnostic
sharing model: in Pagination, two items can share
unitary pieces of data, or symbols, in any nonhierarchical fashion. We showed that with such
overlapping items, or tiles, the familiar tools and
methods of Bin Packing may produce surprising results: for instance, while the family of Any
Fit approximations have no more guaranteed performance, genetic algorithms still behave particularly well in the group-oriented encoding of [7]. We
tested all these algorithms on a large set of random instances, along with an ILP solver, and some
specialized greedy and non-greedy heuristics. The
choice of the best one is not clear-cut, but depends
on both time/quality requirements and the average
multiplicity of the symbols. The latter measure was
proposed as a predictor of the statistical difficulty
of a given instance, and correlated experimentally
with the actual outcome of our various algorithms.
Obviously, this work did not aim to close the
problem, but rather to open it to further research,
by providing the required vocabulary, several theoretical tools, and an extensive benchmark. Indeed, numerous directions should be investigated:
examples of these are worst-case analysis, proof of
lower bounds, elaboration of efficient cuts, etc. To
make Pagination more manageable, a promising
approach restricts it to one single page [8, 17].
16

References
[1] Claude Berge. Graphs and Hypergraphs. Elsevier Science Ltd., Oxford, UK, UK, 1985.
[2] Edward G. Coffman, Jr., Michael R. Garey,
and David S. Johnson. Approximation algorithms for bin packing: a survey. In Dorit S.
Hochbaum, editor, Approximation algorithms
for NP-hard problems, chapter 2, pages 46–93.
PWS Publishing Co., Boston, MA, USA, 1997.
[3] Edward G. Coffman Jr., János Csirik, Gábor Galambos, Silvano Martello, and Daniele
Vigo.
Bin Packing Approximation Algorithms: Survey and Classification, pages 455–
531. Springer New York, New York, NY, 2013.
[4] György Dósa and Jiří Sgall. First Fit bin
packing: A tight analysis. In 30th International Symposium on Theoretical Aspects of
Computer Science (STACS 2013), volume 20,
pages 538–549, Dagstuhl, Germany, 2013.
[5] Mitre C. Dourado, Fabio Protti, and Jayme L.
Szwarcfiter. Complexity aspects of the Helly
property: Graphs and hypergraphs. The Electronic Journal of Combinatorics, #DS17:1–53,
2009.
[6] John Duncan and Lawrence W. Scott. A
branch-and-bound algorithm for pagination.
Operations Research, 23(2):240–259, 1975.
[7] Emanuel Falkenauer and Alain Delchambre. A
genetic algorithm for bin packing and line balancing. In Proceedings of the 1992 IEEE International Conference on Robotics and Automation, pages 1186–1192, 1992.
[8] Aristide Grange, Imed Kacem, Karine Laurent, and Sébastien Martin. On the Knapsack
Problem Under Merging Objects’ Constraints.
In 45th International Conference on Computers & Industrial Engineering 2015 (CIE45),
volume 2, pages 1359–1366, Metz, France,
2015.
[9] Aristide Grange, Imed Kacem, and Sébastien
Martin. Algorithms for the bin packing problem with overlapping items: Dataset and
experimental results. https://github.com/
pagination-problem/pagination.

[10] M. T. Hajiaghayi, K. Jain, K. Konwar, L. C.
2016. DOI 10.1109/TPDS.2016.2641937, 14
Lau, I. I. Măndoiu, A. Russell, A. Shvartspages, to appear.
man, and V. V. Vazirani. The minimum kcolored subgraph problem in haplotyping and [19] Michael Sindelar, Ramesh K. Sitaraman, and
Prashant Shenoy. Sharing-aware algorithms
DNA primer selection. In Proc. Int. Workshop
for virtual machine colocation. In Proceedings
on Bioinformatics Research and Applications,
of the 23rd ACM symposium on Parallelism in
2006.
algorithms and architectures, pages 367–378,
[11] David S. Johnson. Near-Optimal Bin Packing
New York, New York, USA, 2011. ACM Press.
Algorithms. PhD thesis, Massachusetts Insti[20] Emanuel Sperner. Ein satz über untermentute of Technology, Cambridge, 1973.
gen einer endlichen menge. Mathematische
[12] George Karypis and Vipin Kumar. MultiZeitschrift, 27(1):544–548, 1928.
level k-way Hypergraph Partitioning. In ProMathematics of
ceedings of the 36th annual ACM/IEEE De- [21] Apostolos Syropoulos.
Multisets.
Multiset
Processing
SE - 17,
sign Automation Conference, DAC ’99, pages
2235(August):347–358,
2001.
343–348, New Orleans, Louisiana, USA, 1999.
ACM.
[22] David Wilcox, Andrew W. McNabb, and
[13] Michael Kaufmann, Marc Kreveld, and Bettina Speckmann. Graph Drawing: 16th International Symposium, GD 2008, Heraklion,
Crete, Greece, September 21-24, 2008. Revised
Papers, chapter Subdivision Drawings of Hypergraphs, pages 396–407. Springer Berlin
Heidelberg, Berlin, Heidelberg, 2009.
[14] Krista Lagus, Ilkka Karanta, and Juha YläJääski. Paginating the generalized newspapers
— A comparison of simulated annealing and
a heuristic method, pages 594–603. Springer
Berlin Heidelberg, Berlin, Heidelberg, 1996.
[15] Silvano Martello and Paolo Toth. Bin-packing
problem, pages 221–245. Wiley-Interscience series in discrete mathematics and optimization.
J. Wiley & Sons, 1990.
[16] Karl Pearson. Notes on regression and inheritance in the case of two parents. In Proceedings
of the Royal Society of London, volume 58,
pages 240–242, 1895.
[17] Safraz Rampersaud and Daniel Grosu. A
sharing-aware greedy algorithm for virtual machine maximization. In IEEE 13th International Symposium on Network Computing and
Applications, NCA 2014, pages 113–120, 2014.
[18] Safraz Rampersaud and Daniel Grosu.
Sharing-aware online virtual machine packing
in heterogeneous resource clouds. IEEE Transactions on Parallel and Distributed Systems,
17

Kevin D. Seppi. Solving virtual machine packing with a reordering grouping genetic algorithm. In IEEE Congress on Evolutionary
Computation, pages 362–369. IEEE, 2011.

