Workshop on algorithm engineering
Bernard M. E. Moret · ACM SIGACT News · 1997
The Workshop on Algorithm Engineering, first of its name, took place at the University of Venice (La Universit~ di Venezia "Ca' Foscari") on September 11-13, 1997.(Details on the workshop, including a list of participants with addresses and email, final program, etc., can be found at UP~L wwv.dsJ.. unive, it/-wae97/.)The workshop was well attended (54 participants formally registered).Most of the attendees are currently involved in research in the area of algorithm engineering, which, in this particular case, meant the development, experimental testing, and characterization of robust algorithms and data structures for a variety of combinatorial problems.Highlights of the conference were presentations by the LEDA team (Germany) on the current state of the library and plans for its future; by Franco Preparata (now at Brown U.) on a measure of robustness (as measured by the degree of polynomial computations involved) for algorithms, to be ranked at the level of running time and space as a goal in algorithm design; and by Kurt Mehlhorn (Germany) on algorithms designed to work directly with secondary storage (needed for very large data sets).Secondary storage (disk) is increasingly used, even in these days of huge primary memory (several conferees had run test problems on machines with 1GB of primary memory), because of the staggering sizes of certain databases and of the output of large simulations.Computing with secondary storage is almost a lost art: computing pioneers of the 50s and 60s did a lot of it, but it cannot be found in most recent textbooks on algorithms and data structures.Kurt Mehlhorn called for us to measure algorithms, not just in terms of their rlmning time and storage requirements in primary storage, as is traditionally done, but with an additional parameter, the nilmber of disk accesses require to complete the computation.He then proceeded to show that time-optimal (in terms of primary storage) algorithms that generate large number of disk accesses (under a simple model of data storage) can be replace by algorithms with equal asymptotic running time and yet with much smaller or even optimal disk accesses, thereby showing that, at least in some cases, one can have his cake and eat it too.Robustness of computations has long been a concern in numerical computing and has hampered widespread application of the many innovative algorithrn~ in computational'geometry, but has not been of much concern to the discrete algorithm commzmlty until recently.Franco Preparata discussed how lack of robustness can lead, not just to imprecision, but to wrong conclusions and stated that this lack of robustness had led to a loss of credibility for the area of computational geometry.The model he proposed would carry out exact computations, using just the precision