Algorithm Engineering Research Group 

Research Report 1997

The central aim of Algorithms Engineering is the study of the techniques for the design of efficient algorithms and for the formal and experimental analysis of their performance. Computer systems are becoming more and more demanding in terms of performance, due to the increasing complexity of both applications (that, for example, require the repeated solution of large optimization problems on large sets of data), and computer systems (that, for example, require a very efficient management of processors, memories and interconnection networks). In the past twenty years, the theory of algorithms has laid down the principles of algorithms design and of complexity analysis of problems. Now, in order to approach the practical solution of efficiency critical applications, many more aspects have to be addressed, ranging from the study of realistic computation models, to the definition of various types of algorithms that have to perform efficiently in a dynamically changing environment, to the definition of new complexity measures that allow to assess the practical usability of algorithms.

Research work done in the area of Algorithms Engineering is report in five subsections, the first three related to two large and very important problem domains (Graph and combinatorial algorithms, Geometric computing and Distributed and network algorithms) the last two devoted to two important methods of processing information and solving problems in very complex environments.

1. Graph and combinatorial algorithms

In this area the research has been focusing on dynamic graph algorithms, dynamic hypergraph algorithms, and algorithmic techniques for several combinatorial problems.

In [I2-C-13] the authors maintain the information on connectivity in a planar graph during arbitrary sequences of insertions and deletions of edges, and switch-on and switch-off operations on the vertices. They solve the problem in O(log3 n) time per operation, improving sharply on previous approaches.

In [I2-C-12] the authors perform an extensive experimental study of fully dynamic algorithms for the single source shortest path problem in digraphs with positive real edge weights. They report experiments both on random graphs and on real world graphs subject to random sequences of updates.

In [I2-C-11] the authors propose the first semi-dynamic solutions for the single source shortest path problem on digraphs with integer edge weights, and for the breadth first search problem, which are more efficient than recomputing the solution from scratch after each update, taking O(n) amortized time per operation, where n is the number of nodes. Along the same line of research, in [I2-J-3] an incremental algorithm is proposed to maintain a DFS-forest in a directed acyclic graph under a sequence of arc insertions in O(n) amortized time per operation. This compares favorably with the time required to recompute a DFS-forest from scratch. This algorithm relies on an original characterization of a DFS-forest in terms of a relaxed planar embedding of the graph. These techniques have been extended to the decremental maintenance of minimum rank hyperpaths on directed hypergraphs in [I2-C-4].

In [I2-C-9] a semi-dynamic setting for the Temporal Constraint Satisfaction Problem is considered, where one is requested to maintain the path-consistency of a network under a sequence of insertions of new (further) constraints between pairs of variables. An algorithm is presented, running in O(n R3) amortized time on a sequence of Q (n2) insertions, where n is the number of vertices of the network and R is its range (defined as the maximum size of the minimum interval containing all the intervals of a single constraint). The algorithm is general and extendible.

Dynamic algorithms for the on-line maintenance of weighted hypergraphs have been devised with application to satisfiability of propositional Horn formulae with uncertainty in [I2-J-1], where the authors show how to represent a significant class of formulae by weighted directed hypergraphs and present two algorithms that solve the on-line Horn-SAT problem and find a minimum model for the formula working on the dynamic weighted hypergraph representation. These algorithms make increasing assumptions on the formula and the second one solves the on-line Horn-SAT problem with a total time linear in the size of the formula, matching the optimal result for Boolean Horn formulae.
 

2. Geometric computing

The research on Geometric computing followed four main directions.

One main task was the design of robust algorithms for computational geometry, i.e. algorithms that are not affected by numerical errors and that can handle degenerate configurations of the input. In [I2-R-8] and in [I2-C-16] research has focused on developing a methodology for designing robust algorithms with low precision arithmetics demand. In [I2-C-10] the problem of checking the output correctness of several geometric algorithms, including those that compute convex polytopes and those that compute planar subdivisions, is investigated. A new architectural frame for visualization of geometric algorithms over the world wide web is described in [I2-R-5].

A second direction of research is about characterizing and computing proximity drawings of graphs. Such family of drawings include minimum weight triangulations, visibility representations, Gabriel drawings, and rectangle of influence drawings as special cases. The results obtained combine geometric graph theory and efficient algorithm design. The geometric constraints that are taken into account by the algorithms include the clusterization of groups of adjacent vertices in the drawing, and area minimization. The area required by visibility representations and by Gabriel drawings is studied in [I2-J-4] and in [I2-C-17]. Several classes of graphs that admit a rectangle of influence drawing are characterized in [I2-J-5]. The relationship between topology and geometry for well known structures such as minimum weight triangulations and Delaunay triangulations is investigated in [I2-C-14]. The problem of computing orthogonal representations with the minimum number of bends is studied in [I2-R-6].

A third direction of research focused on the study of basic computational geometry problems. In [I2-C-8] the authors consider the problem of maintaining and reporting the maxima of a set of points in the plane in the partially dynamic setting of boundary updates, defined by a movable and resizable vertical window on the point set. The authors present a data structure capable of answering maxima queries in optimal O(k) worst case time, where k is the size of the answer, and an algorithm for maintaining the data structure under boundary updates in O(log n) time per update.

Finally a fourth direction of research applies computational geometry techniques to data base applications. In [I2-R-1] data structures are presented for the efficient implementation of half-space queries in 2 and 3 dimensions, suitable to secondary memory applications.
 

3. Distributed and network algorithms

In this area, applicative problems have been considered. The problem of deciding the feasibility of a scheduling for broadcast transmission under the TDMA protocol is studied in [I2-J-2]. The problem is proved to be NP-hard. Polynomial time distributed algorithms are proved to obtain solutions close to the optimum on practical instances of the problem.

In [I2-C-7] the authors consider the problem of constructing embeddings of 2-dimensional FEM graphs into grids with the goal of minimizing the edge-congestion and dilation and optimize the load. The authors introduce some heuristics, analyze their performance, and present experimental results comparing the heuristics with the methods based on the usage of standard graph partitioning libraries.

In [I2-C-6] the problem of realizing ATM routing schemes with fixed hop-count and minimum load is addressed. Lower bounds for the general case and for fixed connection patterns and networks are presented.
 

4. Complexity and approximation

Due to their intrinsic complexity, for NP-hard optimization problems we cannot hope to find efficient general solution algorithms and we need to restrict ourselves to approximate solutions. Hence, the study of approximate algorithms for NP-hard optimization problems has a considerable importance both from the theoretical point of view and with respect to the practical aim of designing efficient approximation algorithms which are guaranteed to provide a solution within a maximum relative error. In this area three research directions are being pursued.

Along the first direction theoretical aspects of approximability have been studied. In particular the class of problems that can be efficiently approximated by means of local search algorithms has been studied and a new and more powerful local search approximation techniques, that generalizes the standard technique and enlarge the power of this general paradigm, have been developed [I2-R-3]. Using these techniques, in [I2-C-1] the authors give a fully dynamic 5/2-approximate algorithm for the class of Maximum binary conjunctive constraint satisfaction problem, and thus for the Maximum directed cut problem. The proposed algorithm is based on the non-oblivious local search technique and on a neighborhood mapping that allows to change either one item, or all the items in the current solution. Besides, in [I2-C-3] APX-hardness results for several optimization problems on cubic and at-most-cubic graphs that belong to MAX SNP, namely Minimum vertex cover, Maximum independent set, Minimum dominating set and Maximum cut.

Along the second line, approximation algorithms have been designed for specific combinatorial problems. Namely, in [I2-C-2] the minimum independent dominating set problem in bounded degree graphs has been studied, and approximate algorithms based on greedy and local search techniques have been developed. The max and the min weighted satisfiability problems are variants of the standard max satisfiability problem, in which every variable is assigned a non-negative weight and one tries to find a truth assignment satisfying the formula, that maximize or minimize the sum of the weights of the variables set to true. In [I2-R-4] a complete classification of the problems obtained by making restrictions on the size of variables per clause and on the number of occurrences of variables in the clauses is given.

Along the third direction, applicative problems have been considered. In particular, algorithms for integrated prefetching and caching for minimizing stall time in single and parallel disk systems while moving blocks from disk to cache are proposed in [I2-R-2]. In this work approximation algorithms for the parallel disk case are devised through a linear programming formulation of the problem. It is also presented the first polynomial time algorithm for the single disk case, thus settling a basic open problem in the field. The first approximation algorithms with performance guarantee for minimizing the total flow time of a set of jobs released over time in a multiprocessor setting are proposed in [I2-C-15]. The total flow time is the overall time spent in the system by a set of jobs. Approximation algorithms are presented for both the preemptive a and the non-preemptive case. In [I2-R-9] the multicast problem in hierarchical networks with tree topology is studied. Users distributed in the newtwork ask to be connected to various active multicast groups. The first algorithms with constant approximation ratio for maximizing the number of accepted subscriptions without exceeding links capacity are presented in this paper.
 

5. On-line algorithms

The research on On-line algorithms followed two directions.

Along the first direction, on-line algorithms for network routing problems are proposed for various network architectures and communication regimes. In [I2-B-1] a survey of the main results in the field it is presented. The first randomized on-line virtual circuit routing algorithms that achieve both good expected competitive ratio and good variance are proposed in [I2-R-7]. The on-line virtual circuit routing problem is motivated by its application to routing in ATM networks. This paper presents the first study of the competitive ratio - variance trade-off for randomized on-line algorithms. On-line algorithms for multicast communication in trees and meshes topology are presented in [I2-R-9]. A set of users distributed in the network issues in an on-line fashion connection requests to various active multicast groups. The first on-line algorithms with polylogarithmic competitive ratio for the above mentioned network topologies are presented for the case of high bandwidth communication demand. The problem of minimizing the number of wavelength required to accept a sequence of unicast communication requests in Wavelength Division Multiplexing (WDM) optical networks is studied in [I2-C-5]. Algorithms with optimal competitive ratio are proposed for trees, trees of rings and meshes topologies. For arbitrary topology networks, efficient algorithms are proposed when the WDM technology is combined with the Space Division Multiplexing technology that allows parallel fiber optic links.

A second line of research focused on on-line Scheduling algorithms. In particular, the first algorithms with optimal competitive ratio for the problem of minimizing the total flow time of a set of jobs in a multiprocessor setting when preemption is allowed are presented in [I2-R-9] for the on-line version of the problem when jobs are known at their release times.
 

National and International Research Projects

Research in the area of Algorithm Engineering has been supported under various contracts during 1997. In particular: Due both to the well established quality of the research and to the participation to international projects the scientific cooperation in this area has been very active both at national level (University of L'Aquila, University of Rome "Tor Vergata," University of Salerno, IASI-CNR, etc.) and at international level. Perticularly relevant have been the scientific relationships with INRIA (Paris), Charles University (Prague), University of Utrecht, Columbia University, Brown University, University of Maryland, IBM T. J. Watson Research Center, International Computer Science Institute (Berkeley), ETH (Zurich), Tel-Aviv University, INRIA (Sophia Antipolis), Mc Gill University (Canada), Paderborn University (Germany), Carleton University (Canada).
 

Publications

 

Books

[I2-B-1] S. Leonardi. On-line network routing. To appear as a chapter of the book “On-line Algorithms”, A. Fiat and G. Woeginger eds., Springer-Verlag, 1998.

Journals

[I2-J-1] G. Ausiello, R. Giaccio, On-line algorithms for satisfiabillity problems with uncertainty, Theoretical Computer Science, special issue on Uncertainty in Databases and Deductive Systems, vol. 171 (1997), pp. 3-24.

[I2-J-2] M. Bonuccelli, S. Leonardi. Scheduling broadcasts in wireless networks. Telecommunication Systems, Vol. 8, Nos. 2-4 (1997), pp. 211-227.

[I2-J-3] P. G. Franciosa, G. Gambosi, U. Nanni, The incremental maintenance of a Depth-First-Search tree in directed acyclic graphs, Inform. Process. Lett., 61, 1997, 113-120

[I2-J-4] G. Kant, G. Liotta, R. Tamassia, I. G. Tollis, Area Requirement of Visibility Representations of Trees, Inform. Process. Lett., 62, 1997, 81–88.

[I2-J-5] G. Liotta, A. Lubiw, H. Meijer, S. H. Whitesides, The Rectangle of Influence Drawability Problem, Computational Geometry: Theory and Applications, 8 , 1997, 1–22.

Conferences

[I2-C-1] P. Alimonti, Non-oblivious Local Search for MAX 2-CCSP withApplication to MAX DICUT, Proc. 23rd International Workshopon Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science 1335, Springer-Verlag, 2-14, 1997.

[I2-C-2] P. Alimonti, T. Calamoneri, Improved Approximations of Independent Dominating Set in Bounded Degree Graphs, Proc. of the 22nd International Workshop on Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science 1197, Springer-Verlag, 2-16, 1997; submitted to Theoretical Computer Science.

[I2-C-3] P. Alimonti, V. Kann, Hardness of Approximating Problems on Cubic Graphs, Proc. 3rd Italian Conference on Algorithms and Complexity, Lecture Notes in Computer Science 1203, Springer-Verlag, 288-298, 1997; submitted to Theoretical Computer Science.

[I2-C-4] G. Ausiello, P. G. Franciosa, D. Frigioni, R. Giaccio. Decremental Maintenance of Reachability in Hypergraphs and Minimum Models of Horn Formulae. Proceedings of the 8th annual International Symposium on Algorithms and Computation (ISAAC'97), Singapore, December 17–19 1997. Lecture Notes in Computer Science 1350, pp. 122–131.

[I2-C-5] Y. Bartal, S. Leonardi. On-line routing in all-optical networks. Proceedings of the 24th International Colloquium on Automata, Languages, and Programming (ICALP 97), pp. 516-526, Lecture Notes in Computer Science 1256, pp. 516-526, Springer-Verlang, 1997.

[I2-C-6] L. Becchetti, C. Gaibisso. Lower Bounds for the Virtual Path Layout Problem in ATM Networks. Proc. of SOFSEM 97, Lectures Notes in Computer Science, Springer-Verlag, Vol. No. 1338. 1997

[I2-C-7] F. d'Amore, L. Becchetti, S. L. Bezrukov, A. Marchetti Spaccamela, M. Ottaviani, R. Preis, M. Röttger and U. P. Schroeder, On the Embedding of Refinements of 2-dimensional Grids, Proc. of EuroPAR 97, Springer, Lecture Notes in Computer Science 1300, 1997, 950–957.

[I2-C-8] F. d'Amore, P. G. Franciosa, R. Giaccio and M. Talamo, Maintaining maxima under boundary updates, Proc. of Italian Conf. on Algorithms and Complexity (CIAC '97), Springer, Lecture Notes in Computer Science 1203, 1997, 100–109.

[I2-C-9] F. d'Amore, F. Iacobini, On-line algorithms for networks of temporal constraints, Proc. of Work. on Graph-Theoretic Concepts in Computer Science (WG '97), Springer, Lecture Notes in Computer Science 1335, 1997, 144–156.

[I2-C-10] O. Devillers, G. Liotta, F. P. Preparata, R. Tamassia, Checking the Convexity of Polytopes and the Planarity of Subdivisions, Proceedings of the Fifth Workshop on Algorithms and Data Structures (WADS '97) , Lecture Notes Comput. Sci. , 1272 , Springer-Verlag, 1997, 186–199.

[I2-C-11] P. G. Franciosa, D. Frigioni, R. Giaccio. Semi Dynamic Shortest Paths and Breadth First Search in Digraphs. Proceedings of the 14th international Symposium on Theoretical Aspects of Computer Science (STACS'97), Luebeck, Germany, February 27 – March 1 1997. Lecture Notes in Computer Science 1200, pp. 33–46. Full version submitted for publication.

[I2-C-12] D. Frigioni, M. Ioffreda, U. Nanni, G. Pasqualone. Experimental Analysis of Dynamic Algorithms for the Single Source Shortest Path Problem. Proceedings of the 1st Workshop on Algorithm Engineering (WAE'97), Venice, Italy, September 11–13 1997, pp. 54–63. Full version submitted for publication.

[I2-C-13] D. Frigioni, G. F. Italiano. Dynamically Switching Vertices in Planar Graphs. Proceedings of the 5th European Symposium on Algorithms (ESA'97), Graz, Austria, September 15–17 1997. Lecture Notes in Computer Science 1284, pp. 186–199. A full version appears as Tech. Rep. n. TR-203-97 of the EU ESPRIT Long Term Research Project ALCOM-IT, 1997, and has been submitted for publication.

[I2-C-14] W. Lenhart, G. Liotta, Drawable and Forbidden Minimum Weight Triangulations, Graph Drawing (Proc. GD '97), Lecture Notes Comput. Sci. , 1353 , Springer-Verlag, 1998, 1–12.

[I2-C-15] S. Leonardi, D. Raz. Approximating total flow time on parallel machines. Proceedings of the 29th ACM Symposium on Theory of Computing (STOC 97), pp. 110-119, 1997.

[I2-C-16] G. Liotta, F. P. Preparata, R. Tamassia, Robust Proximity Queries: an Illustration of Degree-Driven Algorithm Design, Proc. 13th Annu. ACM Sympos. Comput. Geom.., 1997 , 156–165.

[I2-C-17] G. Liotta, R. Tamassia, I.G. Tollis, P. Vocca, Area requirement of Proximity Drawings, Proceedings of the 3rd Italian Conference on Algorithms and Complexity (CIAC97) , Lecture Notes Comput. Sci., 1203 , Springer-Verlag, 1997, 135–146.

Technical Reports and Submitted Papers

[I2-R-1] P. Agarwal, L. Arge, J. Erickson, P. G. Franciosa, J. S. Vitter, Efficient Searching with Linear Constraints, 17th Symp. on Principles of Database Systems (PODS '98), Seattle, 1998, accepted for presentation.

[I2-R-2] S. Albers, N. Garg, S. Leonardi. Minimizing stall time in single and parallel disk systems. To appear in Proceedings of the 30th Annual ACM Symposium on Theory of Computing (STOC 98), Dallas, 23-26 May, 1998.

[I2-R-3] P. Alimonti, Local Search and Approximability of MAX SNP Problems, Tesi di Dottorato, Dottorato di Ricerca in Informatica, Universita` degli Studi di Roma La Sapienza, IX-97-1, 1997.

[I2-R-4] P. Alimonti, G. Ausiello, L. Giovaniello, M. Protasi, On the Complexity of Approximating Weighted Satisfiability, Rapporto Tecnico, RAP 38.97, Dipartimento di Informatica e Sistemistica, Università degli Studi di Roma “La Sapienza”, 1997.

[I2-R-5] J. E. Baker, I. F. Cruz, G. Liotta, R. Tamassia, Visualizing Geometric Algorithms over the Web, Computational Geometry: Theory and Applications, to appear.

[I2-R-6] G. Di Battista, G. Liotta, F. Vargiu, Spirality and Optimal Grid Drawings, SIAM J. Comput., to appear.

[I2-R-7] S. Leonardi, A. Marchetti-Spaccamela, A. Presciutti and A. Rosen. On-line Randomized Call-Control Revisited. Proceedings of the 9th ACM-SIAM Symposium on Discrete Algorithms (SODA '98), pp. 323-332, 1998.

[I2-R-8] G. Liotta, F. P. Preparata, R. Tamassia, Robust Proximity Queries: an Illustration of Degree-driven Algorithm Design , SIAM J. Comput., to appear.

[I2-R-9] M. Rauch-Henzinger, S. Leonardi. Scheduling multicasts on trees and meshes. Rapporto Tecnico n. 33–97 del Dipartimento di Informatica e Sistemistica dell'Università di Roma “La Sapienza”.
 

AE  Go back to the Home Page of Algorithm Engineering.  DIS  Go back to the Home Page of Dipartimento di Informatica e Sistemistica. 
DIS  For problems or comments about this page, please send email to ae@dis.uniroma1.it. DIS  Search pages of Algorithm Engineering.