Work Area: Algorithms for Parallelism and Efficiency
Keywords algorithms, analysis, complexity, data structures
Start Date: 24 July 1992 / Duration: 36 months / Status: running
[ participants / contact ]
Abstract The ALCOM II project is concerned with the design, analysis, and implementation of efficient computer algorithms; it builds upon the successful work of ALCOM I (3075). The goal of the project is to provide the efficient algorithms which are needed to build competitive information-processing systems.
Algorithmic problems are abundant in many areas of science and technology, eg, in CAD networking, computer graphics and animation, cartography, and in transport systems. Efficient solutions to these algorithmic problems are of vital importance for competitive application systems in these and similar domains. The overall aim of ALCOM II is to provide the efficient algorithms and date structures needed for these solutions.
Continuing the ALCOM I effort, the research in ALCOM II concentrates on the design of sequential, parallel and distributed algorithms, the analysis of algorithms, complexity theory, and on implementation. The consortium's coherent algorithmic approach is based on the following general methods: randomisation and probabilistic design, identification of algorithmic modules, dynamic data structures, and methodology of complexity analysis.
The dissemination of results and know-how is achieved through open schools, publications, an electronic bulletin board, and the disribution of prototype implementations. Prototype implementations were already distributed to several hundred sites.
The project had a successful first year. It achieved the goals set forth in the work plan and is now not only the leading European player in all theoretical aspects of algorithms and complexity but also has significant direct practical impact through its software deliverables ALF, LEDA, LUO, DSS, and PARIX. Over 15 Ph.Ds and over 130 research reports have been completed. It organised workshops on "Algorithms: Implementation, Libraries, and Use" and on "Graph Drawing" and it established an electronic newsletter.
In the area of sequential algorithms we discovered a new randomised algorithm for linear programming whose running time is subexpontential in the number of variables and constraints and does not depend on the size of the coefficients of the constraint matrix. Previously, only algorithms, eg, the Simplex-method, with exponential worst case complexity were known.
In the area of parallel and distributed algorithms we developed a new load-balancing technique. The new technique has the unique feature that it performs well in practice and can be analysed theoretically. Previously, this combination seemed elusive. The new technique has helped to win the Vice championship in Computer Chess.
In the area of analysis of algorithms and complexity we solved a long-standing open problem and determined the exact number of comparators needed to merge two sorted sequences of lenth n. In the area of implementation we further increased the functionality of the LEDA platform for combinatorical computing. The platform is intensively used by several hundred sites worldwide.
ALCOM's research provides algorithms which have the potential of becoming fundamental building blocks for future systems in computer-aided design, computer graphics, symbolic manipulation, robotics, parallel and distributed computing, and VLSI design. The prototype implementations ease the transfer of the project's results to these application domains. The experience ot the first year shows that this potential is real.
Internal information dissemination is secured by the ALCOM electronic newsletter. External dissemination is through our workshops and through our numerous publications. The systems LUO and LEDA are available through anonymous ftp.
Max-Planck-Institut für Informatik - D
Im Stadtwald 15
D-W - 6600 SaarBrücken
Freie Universität Berlin - D
Universität Paderborn - D
rhus Universitet - DK
Universidad Politecnica de Catalunya - E
INRIA-Sophia Antipolis - F
EHESS-CAMS - F
Computer Technology Institute - GR
Universita degli Studi di Roma "La Sapienza" - I
Trinity College Dublin - IRL
Rijksuniversiteit Utrecht - NL
University of Warwick - UK
Prof. Dr. K. Melhorn
tel +49/681 302 5410
fax +49/681 302 5401
ALCOM II - 7141, August 1994
please address enquiries to the ESPRIT Information Desk
html version of synopsis by Nick Cook