Algorithms and Complexity

Foreword This issue of Theory of Computing Systems (TOCS) contains the revised versions of one invited contribution and of six regular contributions to CIAC 2003, the Fifth Italian Conference on Algorithms and Complexity. The conference was organized by the Dipartimentodi Informatica of the Universit`a degli Studi di Roma “La Sapienza” and took place in Roma from May 28 to May 30, 2003. In response to the call for papers for CIAC 2003, 57 papers were submitted, from which the Program Committee selected 23 papers for presentation at the conference from 18 countries. Each paper was evaluated by at least three Program Committee members with the help of 63 external reviewers. In addition to the selected papers, the Organizing Committee invited Charles E. Leiserson (Cambridge), David Peleg (Rehovot), Michael O. Rabin (Cambridge and Jerusalem), John E. Savage (Providence), and Luca Trevisan (Berkeley) to give plenary lectures at the conference. Moreover, three tutorials by David Peleg, Jayme L. Szwarcfiter (Rio de Janeiro), and Luca Trevisan had been offered in the days preceding the conference. The papers included in this section passed through a second referee process and the authors have been asked to revise and possibly extend the conference papers. Here areshort abstract of the selected papers:The paper “Graph-Modeled Data Clustering: Fixed-Parameter Algorithms for Clique Generation” by J. Gramm, J. Guo, F. H¨uffner, and R. Niedermeier presents efficient fixed-parameter algorithms for the NP-complete edge modification problems, in which we ask for the fewest number of additions and/or deletions of edges that make a graph a vertex-disjoint union of cliques. In “Unlocking the Advantages of Dynamic Service Selection and Pricing,” B. Kalyanasundaram, M. Velauthapillai, and J. Waclawsky present practical on-line algorithms to minimize the overall usage cost to mobile users. In their model, service providers are allowed to change service level pricing dynamically and the user has the possibility of changing service level and/or provider for a small fee. The article “Efficient Update Strategies for Geometric Computing with Uncertainty”, by R. Bruce, M. Hoffmann, D. Krizanc, and R. Raman, considers the problem of computing maximal points and the convex hull of a set of moving points in two dimensions. It is assumed that trajectories are not known precisely and algorithms are provided that are at most a constant factor away from the optimum. The study of stable routing algorithms is the subject of the paper “The Impact of Network Structure on the Stability of Greedy Protocols” by D. Koukopoulos, M.Mavronicolas, S. Nikoletseas, and P. Spirakis. The article contains a comprehensive collection of structural results for various greedy routing protocols. The paper “On-Line Stream Merging with Max Span and Min Coverage” by W.-T. Chan, T.-W. Lam, H.-F. Ting, and P. W. H. Wong, introduces the notions of span and coverage for on-line algorithms for merging communication streams (such as, for example, video-on-demand). The authors give a simple greedy algorithm which attains optimal span and coverage. Routers for the IP protocols are dealt with by the paper “XOR-Based Schemes for Fast Parallel IP Lookups” by G. Bongiovanni and P. Penna. The authors present novel algorithmic techniques for exploiting the parallelism of the router and the size of the routing table. The paper “Efficient Data Storage in Large Nanoarrays” by L.-A. J. Gottlieb, J. E. Savage, and A.Yerukhimovich reports on algorithmic aspects of nanoarrays. Specifically, the authors consider the complexity of programming nanoarrays and give hardness results for several variants of the decision problem and for the approximability of the related optimization problem. In addition, the authors give positive results for some specific cases. J. E. Savage gave an invited lecture at CIAC on the role of Theoretical Computer Science in the understanding of electronic nanotechnologies. Anne Condon served as aneditor for this paper. We wish to thank all the authors, the referees, and in particular Alan Selman for his ability in coordinating our activity. GIUSEPPE PERSIANO ROSSELLA PETRESCHI Guest Editors