Wednesday, March 1, 2000
9:15 Welcome and Opening
---------------------------------------------------------------------------------------------------------------------
Session 1 (Chair R.Petreschi)
|
10:00 |
Invited Talk: Giorgio Ausiello On Salesmen, Repairmen, Spiders, and Other Traveling Agents
|
|
11:00 |
TEA/COFFEE BREAK
|
|
11:30 |
Towards the Notion of Stability of Approximation for Hard Optimization Tasks and the Traveling Salesman Problem H. Bockenhauer, J. Hromkovic, R. Klasing, S. Seibert and W. Unger
|
|
12:00 |
An Efficient Algorithm for the Approximate Median Selection Problem S. Battiato, D. Cantone, D. Catalano, G. Cincotti and M. Hofri
|
---------------------------------------------------------------------------------------------------------------------
12:30 LUNCH
---------------------------------------------------------------------------------------------------------------------
Session 2 (Chair P.Crescenzi)
|
14:30 |
Approximating SVPinfty to within Almost-Polynomial Factors is NP-Hard I. Dinur
|
|
15:00 |
Labeling Downtown G. Neyer and F. Wagner
|
|
15:30 |
The Hardness of Placing Street Names in a Manhattan Type Map S. Seibert and W. Unger
|
---------------------------------------------------------------------------------------------------------------------
16:00 TEA/COFFEE BREAK
---------------------------------------------------------------------------------------------------------------------
Session 3 (Chair G.Italiano)
|
16:30 |
The Online-TSP against Fair Adversaries M. Blom, S. Krumke, W. De Paepe and L. Stouge
|
|
17:00 |
Online Strategies for Backups P. Damaschke
|
|
17:30 |
The Online Dial-A-Ride Problem under Reasonable Load D. Hauptmeier, S. O. Krumke and J. Rambau
|
Thursday, March 2, 2000
Session 4 (Chair A.Clementi)
|
9:00 |
Invited Talk: Narsigh Deo Computing a Diameter-Constrained Minimum Spanning Tree in Parallel
|
|
10:00 |
TEA/COFFEE BREAK
|
|
10:30 |
Dynamically Maintaining the Widest k-dense Corridor S. C. Nandy, T. Asano and T. Harayama
|
|
11:00 |
Triangulations without Minimum-Weight Drawing C. A. Wang, F. Y. Chin and B. Yang
|
|
11:30 |
Reconstruction of Discrete Sets from Three or More X-rays E. Barcucci, S. Brunetti, A. Del Lungo and M. Nivat
|
|
12:00 |
Group Updates for Red-Black Trees S. Hanke and E. Soilason-Soininen
|
---------------------------------------------------------------------------------------------------------------------
12:30 LUNCH
---------------------------------------------------------------------------------------------------------------------
Session 5 (Chair R.Silvestri)
|
14:15 |
Faster Exact Solutions for Max2Sat J. Gramm and R. Niedermeier
|
|
14:45 |
Convergence Analysis of Simulated Annealing-Based Algorithms Solving Flow Shop Scheduling Problems K. Steinhofel, A. Albrecht and C. K. Wong
|
|
15:15 |
Invited Talk: Shmuel Zaks Duality in ATM Layout Problems
|
---------------------------------------------------------------------------------------------------------------------
16:15 EXCURSION: Guided Tour to GALLERIA BORGHESE
19:30 SOCIAL DINNER
---------------------------------------------------------------------------------------------------------------------
Friday, March 3, 2000
Session 6 (Chair S.Olariu)
|
9:00 |
Invited Talk: Walter L.Ruzzo Algorithms for a Simple Point Placement Problem
|
|
10:00 |
TEA/COFFEE BREAK
|
|
10:30 |
Extending the Implicit Computational Complexity Approach to the Sub-Elementary Time-Space Classes E. Covino, G. Pani and S. Caporaso
|
|
11:00 |
Semantical Counting Circuits F. Noilhan and M. Santha
|
|
11:30 |
On the Lovasz Number of Certain Circulant Graphs V. Brimkov, B. Codenotti, V. Crespi and M. Leoncini
|
|
12:00 |
The Independence Number of Random Interval Graphs W. F. de la Vega
|
---------------------------------------------------------------------------------------------------------------------
12:30 LUNCH
---------------------------------------------------------------------------------------------------------------------
Session 7 (Chair G.Bongiovanni)
|
14:30 |
Modified Binary Searching for Static Tables D. Merlini, R. Sprugnoli and M. C. Verri
|
|
15:00 |
Speeding up Pattern Matching by Text Compression Y. Shibata, T. Kida, S. Fukamachi, M. Takeda, A. Shinoara, T. Shinoara and S. Arikawa
|
|
15:30 |
QuickHeapsort, an Efficient Mix of Classical Sorting Algorithms D. Cantone and G. Cincotti
|
16:00 End of the Conference
Phone: +39-06-4991-8508/8312 Fax: +39-06-8541842
E-mail:ciac2000@dsi.uniroma1.it