Robert Endre Tarjan - US grants

Abstract The purpose of this project is to discover and to understand efficient data structures and combinatorial algorithms and the tools and techniques by which they can be discovered and analyzed. The goals are four-fold: o to devise specific algorithms and data structures tailored to the needs of various importatnt combinatorial problems, thereby producing more efficient solution methods for these problems; o to develop implementations and perform empirical studies with these new methods and their older competitors, with the aim of understanding their essential properties and developing improved variations; o to perform theoretical studies of the worst- and average-case performance of the methods under consideration, with the aim of being able to predict which method is most suitable in a given situation; o to develop general themes of design and analysis, and to apply these themes systematically in the construction of new algorithms and data structures.

Expeditions in Computing: Understanding, Coping with, and Benefiting from Intractability
Computational intractability imposes a limit on the ability to understand nature and design systems. Intractability is a stumbling block for postmen, travelling salesmen, map colorers, and millions of others who would like to complete their tasks as efficiently as possible, yet it is the foundation of 21st century cryptography, which in turn is a pillar of electronic commerce. In order to understand, manage, and exploit intractability it is imperative that progress be made on proving intractability in many forms and computational models, and on unraveling the interconnections among different forms and uses of intractability. This Expedition will explore an array of diverse but interrelated topics in computational intractability including algorithms, complexity, cryptography, analysis, geometry, combinatorics, and quantum mechanics. A "Center for Intractability," the first of its kind, will be based at Princeton. Addressing some of the deepest and hardest theoretical problems standing in the way of significant advancements in computer science, this Expedition involves a high degree of collegial interactivity through collaborations among geographically local participating institutions. Outreach includes an active "Women in Theory" program as well as programs targeting undergraduate and high-school students.

Algorithms are at the core of computer science. The goal of this research is to design and analyze algorithms for a selection of important and interesting algorithmic problems, chosen primarily from the area of graphs and networks. The ideal is to obtain algorithms that are efficient in theory and practice, and conceptually simple as well -- in short, "elegant" algorithms. For each problem, a systematic exploration of possible solutions will be undertaken. Specific problems to be studied will be selected from among dynamic topological ordering and related problems, planarity testing and related graph problems and data structures, maximum and minimum cost network flow problems, amortized efficiency of binary search trees and related data structures, finding dominators and related problems, and others. The broad impact of the research will be to shed new light on the design space of solutions for specific algorithmic problems and families of problems, to produce new algorithmic and analytical techniques, to provide efficient implementations of old and new algorithms, and to produce comparisions of their empirical performance. In addition, new members of the research and teaching community in the field of algorithm design will be trained, and new approaches and new materials for communicating the important concepts in the field will be developed.