Ebook: Algorithms and Complexity: 4th Italian Conference, CIAC 2000 Rome, Italy, March 1–3, 2000 Proceedings

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 constitutes the refereed proceedings of the 4th Italian Conference on Algorithms and Complexity, CIAC 2000, held in Rome, Italy, in March 2000.
The 21 revised full papers presented were carefully reviewed and selected from 41 submissions; also included are four invited survey papers. Among the topics addressed are combinatorial optimization, graph algorithms, graph computations, complexity theory, diagram design, approximation, scheduling, sorting, computational geometry, searching, and pattern matching.

---

This book constitutes the refereed proceedings of the 4th Italian Conference on Algorithms and Complexity, CIAC 2000, held in Rome, Italy, in March 2000.
The 21 revised full papers presented were carefully reviewed and selected from 41 submissions; also included are four invited survey papers. Among the topics addressed are combinatorial optimization, graph algorithms, graph computations, complexity theory, diagram design, approximation, scheduling, sorting, computational geometry, searching, and pattern matching.
Content:
Front Matter....Pages I-VIII
On Salesmen, Repairmen, Spiders, and Other Traveling Agents....Pages 1-16
Computing a Diameter-Constrained Minimum Spanning Tree in Parallel....Pages 17-31
Algorithms for a Simple Point Placement Problem....Pages 32-43
Duality in ATM Layout Problems....Pages 44-58
The Independence Number of Random Interval Graphs....Pages 59-62
Online Strategies for Backups....Pages 63-71
Towards the Notion of Stability of Approximation for Hard Optimization Tasks and the Traveling Salesman Problem....Pages 72-86
Semantical Counting Circuits....Pages 87-101
The Hardness of Placing Street Names in a Manhattan Type Map....Pages 102-112
Labeling Downtown....Pages 113-124
The Online Dial-a-Ride Problem under Reasonable Load....Pages 125-136
The Online-TSP against Fair Adversaries....Pages 137-149
QuickHeapsort, an Efficient Mix of Classical Sorting Algorithms....Pages 150-162
Triangulations without Minimum-Weight Drawing....Pages 163-173
Dynamically Maintaining the Widest k-Dense Corridor....Pages 174-186
Reconstruction of Discrete Sets from Three or More X-Rays....Pages 187-198
Modified Binary Searching for Static Tables....Pages 199-210
An Efficient Algorithm for the Approximate Median Selection Problem....Pages 211-225
Extending the Implicit Computational Complexity Approach to the Sub-elementary Time-Space Classes....Pages 226-238
Group Updates for Bed-Black Trees....Pages 239-252
Approximating SVP ? to within Almost-Polynomial Factors Is NP-Hard....Pages 253-262
Convergence Analysis of Simulated Annealing-Based Algorithms Solving Flow Shop Scheduling Problems....Pages 263-276
On the Lov?sz Number of Certain Circulant Graphs....Pages 277-290
Speeding Up Pattern Matching by Text Compression....Pages 291-305
Back Matter....Pages 306-315
....Pages 317-317