Length:

Delay:

Incremental Delay:

#Simulations:

Maximal delay:

Observed delay:

Observed total time:

**Coussinet** is a demo illustrating a
technique called **geometric amortization**
for enumeration algorithms introduced in the
paper Geometric
Amortization for Enumeration Algorithms. The result presented in this
paper is about making the delay of enumeration algorithms
more regular.

Coussinet is shipped with a preloaded list example. The list represents the run of an enumeration algorithm. Each entry represents a step of the computation. The 0-entries represent a step of the computation where nothing has been output. The other entries, depicted in green, contain the solution output at this step. For a quick overview, just hit play. You will observe the red circle dancing in a perfectly orchestrated way and discovering solutions in the list. When a solution is outputted, it flashes, appears on the righthand side of the screen and becomes black.

You can execute the computation step by step by hitting the next step button or make the enumeration faster by moving the speed cursor to the right.

If you are eager to try your own examples, you can load a personnalized list from the load list menu (top left of the screen) and run the algorithm on it. The input format is simply a text file where each line corresponds to a step of computation. Empty lines or lines containing only 0 are interpreted as 0-entries (no solution) and the others are interpreted as solutions (you can put any text here). You can repeat the same solutions in your file. If you do, the repeated solution will be output the same number of times it appears in the original list.

Some examples may be found here.

While we present several optimizations to implement geometric amortization efficiently in the paper, this demo is not optimized, this is just a small piece of javascript code manipulating the DOM to illustrate how the algorithm works. It will be very slow on big files (even on files having a moderate size).

We are interested in enumeration algorithms enumerating a
set of size K with the following guarantee: for every t
≤ K, the algorithm has output at least t solutions
after a time p×t. We call p the *incremental
delay* of the algorithm. Observe that there may be
large gaps with no solution outputted in the
algorithm. Take for example an algorithm enumerating S
solutions in S steps, then nothing for S steps and a last
solution. It is not hard to see that the incremental delay
of the algorithm is 2 but that there is a delay of S steps
between the output of the last two solutions. If S is
exponential in the input size, then this algorithm does
not have polynomial delay.

We can however force the delay between the output of two solutions to be more regular. We just add a queue to the algorithm. Each time it finds a solution, it adds it to the queue. Every 2 steps, we pull a solution from the queue and output it. The incremental delay guarantees that the queue is never empty when pulling from it. However, one can observe that the queue can get very large. Indeed, after having simulated S steps of the original algorithm, S solutions have been inserted in the queue while S/2 have been pulled, resulting in a possible exponential blow up of the space used by the algorithm. The goal of geometric amortization is to make the delay between two solutions more regular without blowing up the memory.

In the demo, we represent the run of the original enumeration algorithm as a list. Each entry represents a step of the computation. The 0-entries represent a step of the computation where nothing has been output. The other entries, depicted in green, contain the solution output at this step. We let K be the number of solutions in the list. The incremental delay p of the list is given in the list info section. This is a value such that we have the guarantee that the first t×p entries of the list contain at least t solutions for every t≤K.

Our goal is to output solutions with a regular delay
between them without blowing up the memory. To achieve this,
we run N = 1+(log K) simulations of the original enumeration
algorithm orchestrated in a way that guarantees this
regularity and explore the entiere solution space. The idea
is that simulation i will only output solutions only if it
appears at a position in the list that is between
2^{i}p+1 and 2^{i+1}p. To ensure that each
simulation reaches the end of its zone, we need to
orchestrate them in a specific way described below (see the
paper for all details).

In Coussinet, the N=1+(log K) simulations are represented
by small red circles and are orchestrated following the
technique presented in Algorithm 3 of the paper. The
algorithm move the simulations in the following way:
whenever we start moving simulation i, we give it a budget
of 2p steps. It is represented by a green circle in
Coussinet. If it finds a solution in its zone
[2^{i}p+1; 2^{i+1}p] before exhausting its
budget, it outputs it and stops. We then proceed back to
moving simulation N. If it exhausts its budget without
finding any solution, then we start moving simulation
(i-1). We stop when simulation 0 exhausts its budget without
finding any solution. See the paper for details, and, of
course, a proof of the correction.

*Un coussinet* in French means a small
cushion. This is the perfect tool to delicately amortize
your bottom on a hardwood chair, so is Coussinet for
enumeration algorithms.