Efficient Management of Dynamic Data Structures and On-Line Resource Allocation

DYNDATA - KIT131

Keywords: distributed computing, dynamic data structures, resource management, scheduling network management

Start Date: 1 March 95 / Duration: 36 months

Objectivies and Approach

This collaboration is related to the ALCOM (ALgorithms and COMplexity), ALCOM II and Alcom IT projects carried out under ESPRIT. It proposes to address problems of maintenance of information on the properties of combinatorial structures which change in real time - an area of relevance to the design and management of computer and traffic networks, interactive applications, motion planning, and scheduling. The work will focus on the development of efficient algorithms and data structures for the on-line management of graphs and networks, the on-line management of dynamic data structures and on-line resource allocation. Since most of these problems are intrinsically very complex, the work will also address techniques for the approximate solution of NP-hard problems. The main purpose of the action is to establish a solid cooperation between the EU partners and the Non-EU partner through scientific research, exchanges of visits and joint participation in conferences and meetings

Progress and Results

Until now, attention was directed to the following subjects:

Dynamic data structures and the problem of maintaining a single source shortest path tree and a breadth-first search tree for a directed graph.
On line resource management. Problems such as the on-line maintenance of two-level memory under different hypotheses. Problems concerning requests to sets of pages and multiple threads of requests with and without fairness restrictions, on-line routing and scheduling problems, as well as on-line capital investment problems.
Efficient distributed algorithms with particular reference to efficient routing schemes and efficient algorithms for mutual exclusion in distributed systems.
Dynamic algorithms for the approximate solution of combinatorial optimisation problems such as the Min Weighted Set Cover problem.

Information Dissemination Activities and/or Exploitation

To this moment, the sites have exchange several long visits. Furthermore, joint research work was carried out during the International Workshop on On-line Algorithms held in Dagstuhl in May 1996. A second workshop on the same subject will be organized in Italy in 1998. This will bring together scientists from the ALCOM-IT and the KIT DYNDATA projects, as well as professionals from industry. Besides meetings and workshops, the main vehicle for dissemination of the results achieved in this project is publication in scientific journals and presentation at conferences. For a list of publications arising from this collaboration, please refer to the contact person.

Coordinator

Universita di Roma "La Sapienza"
Roma, I

EU Partners

University of Rome "Tor Vergata", I
University of Utrecht, NL

Non-EU Partners

University of Buenos Aires, BRZ

CONTACT POINT

Prof. Giorgio Ausiello
Tel: +39 6 884 19 23
Fax: +39 6 853 00 849
E-mail: ausiello@dis.uniroma1.it