Algorithms and Complexity

Description

Project Title:
Algorithms and Complexity
Acronym:
ALCOM II
Number:
7141
Work Area:
Algorithms for Parallelism & Efficiency
Coordinator:
Max-Planck-Institut für Informatik
Im Stadtwald 15
D-W - 6600 SaarBrücken
Coordinator Country:
D
Partners
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
Contact Point:
Prof. Dr. K. Melhorn
Telephone:
+49/681 302 5410
Fax:
+49/681 302 5401
E-Mail:
alcom@mpi-sb.mpg.de
Keywords:
algorithms, analysis, complexity, data structures
Start Date:
24 July 1992
Duration:
36 months
Status:
running
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.

AIMS

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.

APPROACH AND METHODS

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.

PROGRESS AND RESULTS

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.

POTENTIAL

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.

LATEST PUBLICATIONS

INFORMATION DISSEMINATION ACTIVITIES

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.

Sven Müßig, last update 07-nov-1995. Your feedback is welcome.