Coussinet

Load list:

List info:

Length:

Delay:

Incremental Delay:

Algorithm info:

#Simulations:

Maximal delay:

Observed delay:

Observed total time:

Controls:

Speed:

Original list

Output

What is it?

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.

How to use Coussinet?

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.

Input format

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).

What does it do and how?

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ⁱp+1 and 2ⁱ⁺¹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ⁱp+1; 2ⁱ⁺¹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.

Why Coussinet?

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.