|
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.
In [I2-C9, I2-R12] the authors propose a uniform approach to deal with incremental problems on digraphs, and with decremental problems on dags. Using this approach the first incremental and decremental solution for the dominator problem are given which are more efficient than recomputing the solution from scratch after each update.
Semi-dynamic algorithms are presented in [I2-C12] for the single source shortest path problem on digraphs with positive real edge weights, that are efficient in the output complexity model, and practical. These results are extended in [I2-R18] to the fully dynamic case.
The problem of maintaining the transitive closure in a directed graph under randomly chosen edge insertions and deletions is considered in [I2-J3]. The complexity bounds of updating and query operations outperform the corresponding worst case off-line bounds.
In [I2-R16] 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-R17] 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.
Algorithms for deciding properties of Petri nets that make use of a hypergraph-based approach are presented in [I2-R6]. Namely the proposed algorithms allow to decide liveness and boundedness of the net, and to dynamically maintains the set of potentially firable transitions for conflict-free Petri nets and the wider classes of series-parallel-conflict-free and series-parallel-nondeterministic-conflict-free Petri nets.
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-R8], 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.
The complexity of bounded spherical orders (i.e. partial orders with a single maximum and a single minimum whose diagram can be drawn on a sphere with no edge crossings) is studied in [I2-J6], and a tight bound of 4 for their Boolean dimension is given. In the case of partial orders with more maximal or more minimal elements it is shown that the Boolean dimension is never greater than 5. These results are obtained by characterizing spherical orders in terms of containment between circular arcs.
One main task was the design, implementation and experimentation of algorithms for computational geometry and graph drawing. In particular, in [I2-R25, I2-R23] research has focused on developing a methodology for designing robust algorithms with low arithmetics demand. In [I2-C4, I2-C5] activity has been devoted to developing a new architectural frame for visualization of geometric algorithms over the world wide web. In [I2-R5] a general scheme is presented for implementing persistency in C++. The scheme is tailored to integrate heterogeneous multidimensional indexing structures. In [I2-C10, I2-R13] extensive experimentation has been carried out on graph drawing algorithms that are frequently used in practical applications such as algorithms for computing orthogonal representations and algorithms for computing directed drawings. The problem of computing orthogonal representations with the minimum number of bends is studied in [I2-R14].
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, rectangle of influence and (-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-R26] and in [I2-R19]. Several classes of graphs that admit a rectangle of influence drawing are characterized in [I2-R24]. Algorithms that compute (-drawings for trees and outerplanar graphs are presented in [I2-R11, I2-C13]. A new definition of proximity drawings is introduced in [I2-R15]. A survey of proximity drawings is in [I2-J5]. An algorithm that receives as input a maximal outerplanar graph and computes as output a set of points whose minimum weight triangulation is isomorphic to the input graph is presented in [I2-J7].
A third direction of research focused on the study of basic computational geometry problems. The problem of computing a pair of axis-parallel rectangles with minimum area that include a given set of polygonal objects is investigated in [I2-J4]. Space and time optimal algorithms that maintain a hive graph between two vertical sweep lines are given in [I2-R3]. In the same dynamic setting, in [I2-R2] it is shown how to maintain the maximas of a set of 2d points in optimal space and time.
Finally a fourth direction of research applies computational geometry techniques to data base applications. More specifically, in [I2-R4] the concept of logical data partitioning in bitemporal databases is introduced, where data are partitioned into blocks according to their temporal properties and independently on the particular application. In this framework, basic user update and query operations are considered, and it is shown how to decompose them into lower level operations within single blocks. The approach increases system efficiency, as substantiated by both theoretical and experimental results.
Along the first direction theoretical aspects of distributed computation have been studied, more specifically, distributed computation in totally synchronous distributed network; this is a synchronous system for which the symmetry breaking problem is unsolvable, and then it is not possible to elect a leader and centralize the computation. In [I2-J2] the problem of finding the extrema in a distributed multiset is considered, consisting of determining the minimum and the maximum value of a multiset whose elements are drawn from a totally ordered universe and stored at the entity of a ring network. A novel extrema-finding algorithm is given that improves the bit-time complexity of the previous known result.
Along the second line, applicative problems have been considered. In [I2-R10] the authors deal with the scheduling of transmissions in TDMA packet radio networks. They show that the problem of deciding the feasibility of a schedule is NP-complete, and propose heuristics that are shown to be close to the optimal solution for randomly generated instances of the problem.
In [I2-C11] the problem of efficiently distributing a mutual exclusive resource in a ring topology network using a token based strategy is considered. The attention is focused on the number of messages per request necessary to allocate the resource, providing a bounded delay between the time at which the request is issued and the time at which the resource is obtained. Two new algorithms are proposed and analyzed with amortized complexity techniques.
In [I2-C8] the authors propose broadcasting algorithms for line digraphs in the telephone model. The new protocols use a broadcasting protocol for a graph G to obtain a broadcasting protocol for the graph LkG, the graph obtained by applying k times, the line digraph operation to G. As a consequence improved bounds for the broadcasting time in De Bruijn, Kautz and Wrapped Butterfly digraphs are obtained.
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-J1]. Besides, in [I2-R1] 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-C1] the minimum independent dominating set problem in bounded degree graphs has been studied, and approximate algorithms based on greedy and local search techniques has been developed. Furthermore, in [I2-R22] the authors propose the first approximation algorithms for the ancient problem of minimizing the total flow time of a set of jobs on parallel machines, for both the preemptive and the non-preemptive case, where the flow time of a job is the difference between completion and release time, and the total flow time is the sum of the flow times of all jobs. Each job must be assigned after a given release time to a machine for a given processing time. In the non-preemptive version, the processing of a job once started cannot be interrupted. In the preemptive version the execution of a job can be interrupted and resumed later on any machine. The algorithm known as Shortest Remaining Processing Time is proved to have a logarithmic approximation ratio for the preemptive case. For the non-preemptive case, a general technique that turns a preemptive solution into a non preemptive solution at the expenses of a O((n) factor is proposed. Unapproximability results for the problem are also presented.
A first direction of research is about telecommunication networks. The on-line call admission control problem in optical networks is studied in [I2-C3]. A sequence of communication requests between two nodes of the network is presented one by one. A communication to be accepted must be assigned with a wavelength and a path connecting the two nodes. The goal is that of maximizing the number of communications accepted. The paper studies several models of optical networks, depending upon the nature of the network switches. The paper then presents randomized algorithms with polylogarithmic competitive ratio for specific topologies both for one direction and bidirectional communication.
In [I2-C6] the authors study the performance of on-line randomized algorithms for routing problems in networks. The paper develops a technique for obtaining lower bounds on the competitive ratio of randomized algorithms for a wide class of on-line graph optimization problems: induced subgraph satisfying a hereditary property, edge-disjoint paths, graph coloring, path coloring. Irrespective of the time complexity, an ((n() lower bound on the competitive ratio of randomized on-line algorithms is shown for any of these problems. These results are then applied to find lower bounds for on-line virtual circuit and optical routing problems.
On-line routing in WDM (wavelength division multiplexing) optical networks is studied in [I2-R9]. A sequence of requests arrives over time, each is a pair of nodes to be connected by a path. The problem is to assign a wavelength and a path to each pair, so that no two paths sharing a link are assigned the same wavelength, with the goal of minimizing the number of wavelengths used to establish all connections. The paper gives on-line algorithms with logarithmic competitive ratio for trees, trees of rings and meshes topologies, and almost matching lower bounds. The paper also considers the Space Division Multiplexing technology where every edge is associated with parallel links. For arbitrary networks with a logarithmic number of parallel links an on-line algorithm is presented with logarithmic competitive ratio.
A second direction of research focused on scheduling and routing problems. A version of multiprocessor scheduling is considered in [I2-C7], with the special feature that jobs may be rejected at a certain penalty. In the on-line version the jobs arrive one by one and we have to schedule or reject a job before we have any information about future jobs. The objective is to minimize the makespan of the schedule for accepted jobs plus the sum of the penalties of rejected jobs. The main result is a 1+(( 2.618 competitive algorithm for the on-line version of the problem, where ( is the golden ratio. A matching lower bound is also provided.
In [I2-R7] the authors deals with the problem of efficiently serving a set of requests that are presented in an on-line fashion in a metric space. A traveling salesman must update its route every time a new request is communicated. The goal is that of minimizing the time needed to serve all the presented requests. This work presents competitive algorithms for the cases in which the metric space is arbitrary or the real line.
The problem of making capital investments in machines for manufacturing a product is studied in [I2-C2]. Opportunities for investment occur over time, every such option is associated with a capital cost for a machine and a resulting productivity gain, i.e. a lower production cost for one unit of product. The goal is that of minimizing the total production and capital costs when future demand for the product being produced and investment opportunities are unknown. Optimal logarithmically competitive algorithms are proposed for the general case, while for a restricted version constant competitive bounds are proved.
A last task was the development of general techniques for the analysis of on-line problems. In this setting, in [I2-R20] a general technique is proposed to devise upper and lower bounds for on-line resource management problems and show its applications to a number of routing and scheduling problems.
A general methodology based on linear programming to model a wide class of on-line routing and scheduling problems is also presented in [I2-R21]. Efficient algorithms, whose logarithmic competitive ratio is logarithmic is optimal up to a constant factor, are presented for the maximization and the minimization version of the problem. This methodology finds applications to virtual circuit routing, packet routing, multiprocessor scheduling and shop-scheduling problems.
[I2-J2] P. Alimonti, P. Flocchini, N. Santoro, Finding the Extrema in a Distributed Multiset, Journal of Parallel and Distributed Computing 37, 123-133, 1996.
[I2-J3] P. Alimonti, S. Leonardi and A. Marchetti Spaccamela, Average case analysis of fully dynamic reachability for directed graphs, RAIRO Journal on Theoretical Informatics and Applications, vol 30, n. 4, 1996, pp. 305-318.
[I2-J4] B. Becker, P. G. Franciosa, S. Gschwind, S. Leonardi, T. Ohler, P. Widmayer, Enclosing a set of objects by two minimum area rectangles, Journal of Algorithms, 21, 1996, pp.520-541.
[I2-J5] P. Bose, W. Lenhart, G. Liotta, Characterizing Proximity Trees, published in the journal Algorithmica, Special Issue on Graph Drawing, vol. 16, no. 1, 1996. Springer-Verlag, New York.
[I2-J6] G. Brightwell, P. G. Franciosa, On the boolean dimension of spherical orders, Orders, 13, 1996, pp.233-243.
[I2-J7] W. Lenhart, G. Liotta, Drawing Outerplanar Minimum Weight Triangulations, Journal Information Processing Letters, vol. 57, pp. 253-260, 1996. Elsevier, Amsterdam.
[I2-C2] Y. Azar, Y. Bartal, E. Feuerstein, A. Fiat, S. Leonardi A. Rosn, On capital investment, Proc. of the 23rd International Colloquium on Automata, Languages, and Programming (ICALP 96), Lecture Notes in Computer Science 1099, pp. 429-441, July 1996. Submitted to Algorithmica, special issue on Computational Finance.
[I2-C3] B. Awerbuch, Y. Azar, A. Fiat, S. Leonardi A. Rosn, On-line competititive algorithms for call control in optical networks, Proceedings of the 4th Annual European Symposium on Algorithms (ESA 96), Lecture Notes in Computer Science 1136, pp. 431-444, 1996.
[I2-C4] J. E. Baker, I. F. Cruz, G. Liotta, R. Tamassia, Animating Geometric Algorithms Over the Web, Proceedings of 12th Annual Symposium on Computational Geometry, pp. C3-C4, 1996. ACM Press, New york.
[I2-C5] J. E. Baker, I. F. Cruz, G. Liotta, R. Tamassia, The Mocha Algorithm Animation System, Proceedings of the Workshop on Advanced Visual Interfaces, AVI'96, pp. 248-250, 1996. ACM Press, New york.
[I2-C6] Y. Bartal, A. Fiat, S. Leonardi, Lower bounds for on-line graph problems with application to on-line circuit and optical routing, Proc. of the 28th ACM Symposium on Theory of Computing (STOC 96), pp. 531-540, May 1996. Submitted to Random Structures and Algorithms.
[I2-C7] Y. Bartal, S. Leonardi, A. Marchetti-Spaccamela, L. Stougie, J. Sgall, Multiprocessor scheduling with rejection, Proc. of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 96), pp. 95-103, 1996. Submitted to SIAM Journal on Discrete Mathematics.
[I2-C8] J.C.Bermond, X. Munoz, A. Marchetti-Spaccamela, Induced Broadcasting Algorithms in Iterated Line Digraphs, Proc. EUROPAR 96, Lyon,LNCS Springer-Verlag, 1996.
[I2-C9] S. Cicerone, D. Frigioni, U. Nanni, F. Pugliese, Counting Edges in a Dag, Proceedings of the 22nd International Workshop on Graph Theoretic Concepts in Computer Science (WG'96), Cadenabbia (Como), Italy, June 12-14 1996. Lecture Notes in Computer Science.
[I2-C10] G. Di Battista, A. Garg, G. Liotta, A. Parise, R. Tamassia, E. Tassinari, F. Vargiu, L. Vismara, Drawing Directed Graphs: An experimental Study, Proceedings of Graph Drawing 1996, Lecture Notes in Computer Science.
[I2-C11] E. Feuerstein, S. Leonardi, A. Marchetti-Spaccamela, N. Santoro, Efficient token-based control in rings, Proc. of the 15th ACM Symposium on Principles of Distributed Computing (PODC 96), p. 154, May 1996.
[I2-C12] D. Frigioni, A. Marchetti-Spaccamela, U. Nanni, Fully Dynamic Output Bounded Algorithms Single Source Shortest Path Problem, Proceedings of the 7th annual ACM-SIAM Symphosium on Discrete Algorithms (SODA'96), Atlanta, Georgia, USA, January 28-30 1996, pp. 212-221.
[I2-C13] W. Lenhart, G. Liotta, Proximity Drawings of Outerplanar Graphs, Proceedings of Graph Drawing 1996, Lecture Notes in Computer Science.
[I2-R2] F. d'Amore, P. G. Franciosa, R. Giaccio, M. Talamo, Maintaining maxima under boundary updates, Proceedings of the 3rd Italian Conference on Algorithms and Complexity (CIAC '97), Rome, Italy, March 12-14, 1997. Lecture Notes in Computer Science, to appear.
[I2-R3] F. d'Amore, R. Giaccio, Simplified hive-graphs with boundary updates, Technical report 05.96, Univ. "La Sapienza", Roma, Dipartimento di Informatica e Sistemistica, maggio 1996.
[I2-R4] F. d'Amore, R. Giaccio, Data partitioning in bitemporal databases, Technical report 06.96, Univ. "La Sapienza", Roma, Dipartimento di Informatica e Sistemistica, maggio 1996.
[I2-R5] F. d'Amore, R. Giaccio, A. Villari, A simple and effective way to implement persistency in an object-oriented environment, Technical report 05.96, Univ. "La Sapienza", Roma, Dipartimento di Informatica e Sistemistica, maggio 1996.
[I2-R6] P. Alimonti, E. Feuerstein, U. Nanni, Linear Time Algorithms for Liveness and Boundedness for Conflict-Free Petri Nets and Generalization, submitted a Theoretical computer Science.
[I2-R7] G. Ausiello, E. Feuerstein, S. Leonardi, L. Stougie, M. Talamo, Algorithms for the on-line traveling-salesman, Submitted to Algorithmica.
[I2-R8] 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-R9] Y. Bartal, S. Leonardi, On-line routing in all-optical networks, Submitted to the 24th International Colloquium on Automata Languages and Programming (ICALP 97), 1997.
[I2-R10] M.A. Bonuccelli, S. Leonardi, On-scheduling variable length broadcasts in packet radio networks, To appear in Telecommunication Systems, special issue on Satellite Communication Systems and Networks, 1997.
[I2-R11] P. Bose, G. Di Battista, W. Lenhart, G. Liotta, Proximity Constraints and Representable Trees, Dipartimento di Discipline Scientifiche, Sezione Informatica, Universit degli Studi di Roma III, RT-INF-9-96, 1996.
[I2-R12] S. Cicerone, D. Frigioni, U. Nanni, F. Pugliese, Counting Edges in a Digraph, Tech. Rep. n. TR-075-96 of the EU ESPRIT Long TermResearch Project ALCOM-IT, 1996. Submitted for the pubblication.
[I2-R13] G. Di Battista, A. Garg, G. Liotta, R. Tamassia, E. Tassinari, F. Vargiu, An Experimental Comparison of Four Graph Drawing Algorithms, accepted for publication in Journal of Computational Geometry: Theory and Applications.
[I2-R14] G. Di Battista, G. Liotta, F. Vargiu, Spirality and Optimal Grid Drawings, accepted for publication in SIAM Journal on Computing.
[I2-R15] G. Di Battista, G. Liotta, S.H. Whitesides, The Strength of Weak Proximity, Dipartimento di Discipline Scientifiche, Sezione Informatica, Universit degli Studi di Roma III, RT-INF-8-96, 1996. Roma.
[I2-R16] P. G. Franciosa, D. Frigioni, R. Giaccio, Semi-Dynamic Shortest Paths and Breadth First Search in Digraphs, Proceedings of the 14th International Symphosium on Theoretical Aspects of Computer Science (STACS'97), Luebeck, Germany, February 27 - March 1 1997. Lecture Notes in Computer Science, to appear. Also appeared as Technical Report 105, Universit di L'Aquila, Dipartimento di Matematica Pura e Applicata, marzo 1996.
[I2-R17] P. G. Franciosa, G. Gambosi, U. Nanni, The incremental maintenance of a Depth-First-Search tree in directed acyclic graphs, To appear in Information Processing Letters.
[I2-R18] D. Frigioni, A. Marchetti-Spaccamela, U. Nanni, Semi-dynamic Algorithms for Maintaining Single Source Shortest Path Trees, Algorithmica - Special Issue on Dynamic Graph Algorithms, to appear.
[I2-R19] G. Kant, G. Liotta, R. Tamassia, I.G. Tollis, Area Requirement of Visibility Representations of Trees, accepted for publication in the journal: Information Processing Letters.
[I2-R20] S. Leonardi, On-line resource management with application to routing and scheduling, PhD Thesis, Universit di Roma "La Sapienza", 1996.
[I2-R21] S. Leonardi, A. Marchetti-Spaccamela, On-line resource management with applications to routing and scheduling, Submitted to Algorithmica.
[I2-R22] S. Leonardi, D. Raz, Approximating Total Flow Time on Parallel Machines, To appear in the Proc of the 29th ACM Symposium on Theory of Computing (STOC 97), 1997.
[I2-R23] G. Liotta, Low degree algorithms for Computing and Checking Gabriel Graphs, technical report CS-96-28, Center for Geometric Computing, Department of Computer Science, Brown University Providence (USA).
[I2-R24] G. Liotta, A. Lubiw, H. Meijer, S.H. Whitesides, Classes of Rectangle of Influence Drawable Graphs, Department of Computer Science, Brown University, CS-96-22, 1996. Providence (USA).
[I2-R25] G. Liotta, F. P. Preparata, R. Tamassia, Robust Proximity Queries: an Illustration of Degree-driven Algorithm Design, accepted for publication in SIAM Journal on Computing. Also available as technical report CS-96-16, Center for Geometric Computing, Department of Computer Science, Brown University Providence (USA). To appear in Proceedings of the thirteenth Annual Symposium on Computational Geometry, ACM Press, 1997.
[I2-R26] G. Liotta, R. Tamassia, Y.Tollis, P. Vocca, Area Requirement of Gabriel Drawings, to appear in the proceedings of CIAC97, Lecture Notes in Computer Science.
| |
Go back to the Home Page of Algorithm Engineering. | |
Go back to the Home Page of Dipartimento di Informatica e Sistemistica. | |
| |
For problems or comments about this page, please send email to ae@dis.uniroma1.it. | |
Search pages of Algorithm Engineering. |