Geographical Information Systems are becoming increasingly important to geologists, geographers, and urban and environmental planners, amongst others. Although there is an increasing number of such systems available on the market, many questions of a theoretical nature need to be addressed, because of the inherently large amounts of data and the lack of appropriate models and languages. Also, there is a need for flexible and efficient usage of GIS, thus permitting their application in a broad range of new areas, such as navigation systems for transport and the automotive industry. ESPRIT Working Groups provide a structure that enables researchers to meet, interact and share research results, thus providing a platform for ad dressing fertile research areas with significant industrial promise. This par ticular volume is the result of a workshop organised by the "Basic GOODS" Working Group. The challenge has been to define richer and more powerful data definition and manipulation languages, and also to develop new and efficient algorithms. The challenge has been met, as presented in this volume, and the Working Group has succeeded in laying a good foundation for future research and eventual applications. We look forward to seeing the results of the recently launched "AMUSING" project, which will build on this foundation."

The papers in this volume were presented at the Fourth Italian Conference on Algorithms and Complexity (CIAC 2000). The conference took place on March 1-3, 2000, in Rome (Italy), at the conference center of the University of Rome \La Sapienza." This conference was born in 1990 as a national meeting to be held every three years for Italian researchers in algorithms, data structures, complexity, and parallel and distributed computing. Due to a signi cant participation of foreign reaserchers, starting from the second conference, CIAC evolved into an international conference. In response to the call for papers for CIAC 2000, there were 41 subm- sions, from which the program committee selected 21 papers for presentation at the conference. Each paper was evaluated by at least three program committee members. In addition to the selected papers, the organizing committee invited Giorgio Ausiello, Narsingh Deo, Walter Ruzzo, and Shmuel Zaks to give plenary lectures at the conference. We wish to express our appreciation to all the authors of the submitted papers, to the program committee members and the referees, to the organizing committee, and to the plenary lecturers who accepted our invitation.

This book is an up-to-date documentation of the state of the art in combinatorial optimization, presenting approximate solutions of virtually all relevant classes of NP-hard optimization problems. The well-structured wealth of problems, algorithms, results, and techniques introduced systematically will make the book an indispensible source of reference for professionals. The smooth integration of numerous illustrations, examples, and exercises make this monograph an ideal textbook.