==================================================================== ==================================================================== Camil Demetrescu University of Rome "La Sapienza" Dynamic Graph Algorithms In many applications of graph algorithms, including communication networks, VLSI design, graphics, and assembly planning, graphs are subject to discrete changes, such as additions or deletions of edges or vertices. In the last two decades there has been a growing interest in such dynamically changing graphs, and a whole body of algorithms and data structures for dynamic graphs has been discovered. This talk is intended as an overview of this field. ==================================================================== Ramesh Hariharan IISc Maintaining Steiner Edge Connectivity Given an undirected graph and a subset of its vertices (referred to a Steiner vertices), the talk will describe algorithms for determining and maintaining the edge connectivity of these vertices under insertions. ==================================================================== Sandeep Sen IIT Delhi. Dynamic Algorthms for Shortest Paths and Transitive Closures Well studied graph problems like transitive closure and shortest paths are considerably more complicated when we try to tackle them in a dynamic environment, namely, addition and/or deletion of edges. The use of random sampling and randomization have had significant impact both in terms of efficiency and simplicity. In this talk, we will attempt a guided tour of these techniques and highlight their applications to different reachability problems. ==================================================================== ==================================================================== Lars Arge Aarhus University and Duke University Results and challenges in I/O-efficient Algorithms As the memory system of modern computers become more complex, it is increasingly important to design algorithms that are sensitive to the structure of memory. One of the essential features of modern memory systems is that they consist of a hierarchy of several levels of cache, main memory, and disk, with access times that can vary by several orders of magnitude. To amortize the large access time of memory levels far away from the processor, memory systems often transfer data between memory levels in large blocks. Thus it is becoming increasingly important to design algorithms with high data locality in their memory access patterns, i.e., algorithms that are "memory-aware". In the last decade, a lot of algorithms research has been done in two-level memory models. One main reason for this is that many modern applications store and process datasets much larger than the main memory of even state-of-the-art high-end machines; in such cases the block transfers (I/Os) between main memory and disk is often the performance bottleneck. In this talk, we will give an overview of result and developments in the area of algorithms and data structures for two-level memory models (that is, in I/O-efficient algorithms and data structure). We will especially discuss recent geometric data structure and graph algorithm results, as well as the major challenges in these areas. We will also briefly discuss the challenges in extending two-level results to multi-level models. ==================================================================== Roberto Grossi University of Pisa Implicitness in Dynamic Data [Structures] Implicit data structures maintain n keys into an array of n memory cells, one key per cell. They support dictionary operations---search, insert, delete---by just using O(1) additional memory cells for running the operations (besides the n cells storing the keys). The keys can only be compared and read/written, without any hashing or bit manipulation permitted. Williams' heap is a well known textbook example but it does not support optimal searching. Defined in 1980 by Munro and Suwanda, implicit data structures are intimately related to permutations. Put it into other words, an implicit data structure IS a permutation of the keys plus O(1) memory cells of workspace. While memory cells in regular data structures can be classified as either storing data or auxiliary information (pointers, balance information, etc.), implicit data structures go beyond this dichotomy and permute the keys for encoding what is needed to support the operations. For a given set of n keys, there are potentially n! implicit data structures. The challenge is to study which permutations are quickly searchable and maintainable in a dynamic setting. Only recently operations in implicit data structures for the dictionary problem have been shown to exhibit the same computational cost as that of regular data structures, notwithstanding the strict limitations imposed by the model. We describe how to dynamically maintain some of these permutations within optimal bounds (amortized, worst-case, in main memory, in external memory, cache-oblivious). We also prove that the permutations yielding the sorted order are not the best in this sense, especially for long keys. Joint work with Gianni Franceschini ==================================================================== Irene Finocchi University of Rome Sorting and Searching in the Presence of Memory Faults We address the design of algorithms resilient to memory faults, i.e., algorithms that, despite the corruption of some memory values during their execution, are able to produce a correct output on the set of uncorrupted values. In this framework, we consider two fundamental problems: sorting and searching. In particular, we prove that any O(n log n) comparison-based sorting algorithm can tolerate at most O((n log n)^{1/2}) memory faults. Furthermore, we present one comparison-based sorting algorithm with optimal space and running time that is resilient to O((n\log n)^{1/3}) faults. We also prove polylogarithmic lower and upper bounds on fault-tolerant searching. Joint work with G. F. Italiano ==================================================================== Haim Kaplan Tel Aviv University Online One-Dimensional Conflict-Free Coloring We consider an online version of the conflict-free coloring of a set of points on the line, where each newly inserted point must be assigned a color upon insertion, and at all times the coloring has to be conflict-free, in the sense that in every interval there is a point with a unique color. We present several deterministic and randomized algorithms for achieving this goal, and analyze their performance, that is, the maximum number of colors that they need to use, as a function of the number $n$ of inserted points. joint work with Amos Fiat, Meital Levy, Ji\v{r}\'i Matou\v{s}ek, Elchanan Mossel, J\'anos Pach, Micha Sharir, Shakhar Smorodinsky Uli Wagner, Emo Welzl ==================================================================== ==================================================================== Mark de Berg TU, Eindhoven Kinetic Data Structures -- Overview and Recent Developments In many areas of computer science one has to store, analyze and/or manipulate geometric data. More and more often this involves objects in motion. Hence, the study of geometric data structures for moving objects has in the past few years attracted a lot of attention in computational geometry, especially since the introduction of the kinetic data structure (KDS) framework. In this talk I will describe the KDS framework, give an overview of the results that have been obtained in this area, and present some recent developments. ==================================================================== Tamal K. Dey The Ohio State University Dynamic Meshing of Deformable Surfaces The need for maintaining a valid mesh for a deformable surface is ubiquitous in simulations dealing with macrostructures such as fluids as well as microstructures such as molecules. As the surface changes its geometry and topology, the mesh approximating it should make appropriate adaptations in its connectivity. Specifically, the questions are how to insert, delete and connect vertices so that (i) the underlying space of the mesh maintains the topology of the deforming surface; (ii) it maintains a small Hausdorff distance to the surface and (iii) the quality of the mesh triangles remains good. In this talk we will present a general scheme of achieving these goals using the tools recently developed for Voronoi/Delaunay based surface reconstructions. ==================================================================== Sariel Har-Peled UIUC Dynamic Approximate Nearest Neighbor in Low and High Dimension We will survey known results about ANN in the dynamic settings. We will also present new results about how to maintain the ANN data-structure of Indyk and Motwani [1998], under insertions and deletions. Although such a result was mentioned by [IM98], it was never described in detail. This is a work in progress, and additional results might be described. ==================================================================== ==================================================================== Sudipto Guha University of Pennsylvania Dynamic Data and Stream Algorithms In this talk we will explore data stream algorithms in context of dynamic data. In particular we would investigate algorithms based on maintaining linear projections. We would focus on finding largest eigenvalues and histogram construction. Along with them we would investigate some of the tools required for iterated algorithms based on linear projections. ==================================================================== Piotr Indyk MIT Dynamic Streaming Algorithms ************ Info missing ***************** ==================================================================== Kasturi Varadarajan University of Iowa Core-Sets for Streaming and Kinetic Settings Core-sets have emerged as a powerful paradigm for approximating the solution to several optimization problems. In this paradigm, one obtains an efficient approximation algorithm by first computing a small subset of the input and then solving the optimization problem on the subset using a relatively inefficient exact/approximation algorithm. We will look at some kinds of problems to which this paradigm is applicable, and then see how the paradigm can be extended to solving the same problems in a kinetic setting, where the input objects move in known trajectories, and in a streaming setting, where the input objects form a data stream that is too large to store in memory. ==================================================================== ====================================================================