#
Keynote Speakers

Peter van Emde Boas (University of Amsterdam, The Netherlands)

##
**vEB Trees, 39 Years After**

**Abstract: **

The van Emde Boas tree is a data structure which supports the full repertoire of instructions on a single dynamic subset A of the finite set {0..u-1}, called the universe, with a worst case processing time of O(loglog(u)) for each instruction. The instructions involved include Insert, Delete, Member, Max, Min, Predecessor and Successor as well as composite instructions like Extract_Min. The complexity bound O(loglog(u)) refers to the size of the universe rather than the size n of the manipulated set A .

Since these instructions are sufficient to sort a subset of this universe, at first sight this complexity bound seems to violate the well known Ω(log(n)) lower bound for comparison base sorting algorithms. This is not a real violation since the data structure is based on direct access rather than comparison instructions. For very sparse subsets A, where n = O(log(u)), the structure is not more efficient than comparison based structures like balanced trees. However, for dense subsets the processing complexity O(loglog(u)) = o(log(n)), an

improvement for preserving order in a dynamic set. In 1974 this was not believed to be possible.

In this presentation I want to explain how this structure was discovered 39 years ago, and to compare the original ideas with modern descriptions as presented for example in the third edition of the textbook “Introduction Algorithms” by Cormen, Leiserson, Rivest & Stein.

The vEB data structure was first developed by me in the fall of 1974 during a short residence at Cornell University. The field of algorithms and data structures at that time was still young.

The foundational textbook on Analysis of Algorithms by Aho, Hopcroft and Ullman had just appeared and I had decided to study this book in order to widen my area of interest. The combination of being an outsider in the field, and its youth enabled me to start working on open problems having read just a few chapters of this book.

It took almost a year and help from my students Kaas & Zijlstra before the complicated algorithms implementing the instructions in the original design had been made transparent.

Two years later its unreasonable super linear space consumption had been eliminated. This space consumption was caused by the details of the machine model (RAM) used in the Aho ea. book which had been accepted as the standard model for analysis of algorithms at that time. The naïve implementation of the data structure uses multiplicative instructions for the purpose of address calculations which are forbidden in this machine model. Consequently the van Emde Boas trees were originally presented in a machine model based on pointers. Later it would be shown that the O(loglog(u)) operation time is optimal for pointer based models.

Derviş Karaboğa (Erciyes University, Computer Engineering Department, Turkey)

##
The past, present and future of Artificial bee colony - ABC- Algorithm

###
**Abstract: **

Swarm intelligence (SI) is briefly defined as the collective behaviour of decentralized and selforganized swarms. The well known examples of this type swarms are bird flocks, fish schools and the colony of social insects such as termites, ants, bees etc. Two SI based optimization approaches introduced in 1990s, which are based on the behaviour of ant colony (Ant Colony Optimization-ACO) and fish schooling/bird flocking (Particle Swarm Optimization-PSO), have highly attracted the interest of researchers. Although the swarm intelligence features are clearly seen in honey bee colonies, unfortunately the researchers have recently, especially from the beginning of 2000s, started to be interested in the behaviour of these swarm systems. During a decade, several algorithms have been developed depending on different intelligent behaviours of honey bee swarms. Among those, artificial bee colony (ABC) is the one which has been most widely studied on and applied to solve the real world problems, so far (http://www.scholarpedia.org/article/Artificial_bee_colony_algorithm). Day by day the number of researchers being interested in ABC algorithm increases rapidly. The purpose of this speech is to provide a broad overview of SI and SI models and then to focus on the principles of Artificial Bee Colony. The simple actions executed by the individual agents in ABC and the differences between ABC and other well-known optimization algorithms will be discussed in detail.

The presentation also includes the recent advances with ABC and the discussions with its future.

#
Workshops

Luigi Laura (University La Sapienza Rome, Italy)

##
Dealing with large and massive scale graphs or: my graph doesn't fit in RAM!

###
**Abstract: **

What happens when we deal with large and massive scale graphs, i.e. graphs that do not fit in the main memory?

In this talk we explore some modern alternative computation models: external memory, streaming, mapreduce and pregel-like models. We show that, in these settings, graph problems considered "solved" in the traditional computational model - read the input, compute the solution, print the output - need the development of new techniques.

Loukas Georgiadis (University of Ionanina, Greece)

##
Graph Algorithms: Theory and Practice

###
**Abstract**: TBA

###

##
Special Session on European Grid Infrastructure and Grid Computing

Silvio Pardi (European Grid Infrastructure)