4. CIAC 2000: Rome, Italy

Invited Presentations

• Giorgio Ausiello, Stefano Leonardi, Alberto Marchetti-Spaccamela:
  On Salesmen, Repairmen, Spiders, and Other Traveling Agents. 1-16
  
• Narsingh Deo, Ayman Abdalla:
  Computing a Diameter-Constrained Minimum Spanning Tree in Parallel. 17-31
  
• Joshua Redstone, Walter L. Ruzzo:
  Algorithms for a Simple Point Placement Problem. 32-43
  
• Shmuel Zaks:
  Duality in ATM Layout Problems. 44-58
  

Regular Presentations

• Wenceslas Fernandez de la Vega:
  The Independence Number of Random Interval Graphs. 59-62
  
• Peter Damaschke:
  Online Strategies for Backups. 63-71
  
• Hans-Joachim Böckenhauer, Juraj Hromkovic, Ralf Klasing, Sebastian Seibert, Walter Unger:
  Towards the Notion of Stability of Approximation for Hard Optimization Tasks and the Traveling Salesman Problem. 72-86
  
• Fabrice Noilhan, Miklos Santha:
  Semantical Counting Circuits. 87-101
  
• Sebastian Seibert, Walter Unger:
  The Hardness of Placing Street Names in a Manhattan Type Map. 102-112
  
• Gabriele Neyer, Frank Wagner:
  Labeling Downtown. 113-124
  
• Dietrich Hauptmeier, Sven Oliver Krumke, Jörg Rambau:
  The Online Dial-a-Ride Problem under Reasonable Load. 125-136
  
• Michiel Blom, Sven Oliver Krumke, Willem de Paepe, Leen Stougie:
  The Online-TSP against Fair Adversaries. 137-149
  
• Domenico Cantone, Gianluca Cincotti:
  QuickHeapsort, an Efficient Mix of Classical Sorting Algorithms. 150-162
  
• Cao An Wang, Francis Y. L. Chin, Bo-Ting Yang:
  Triangulations without Minimum-Weight Drawing. 163-173
  
• Jens Gramm, Rolf Niedermeier:
  Faster Exact Solutions for MAX2SAT. 174-186
  
• Subhas C. Nandy, Tomohiro Harayama, Tetsuo Asano:
  Dynamically Maintaining the Widest k -Dense Corridor. 187-198
  
• Elena Barcucci, Sara Brunetti, Alberto Del Lungo, Maurice Nivat:
  Reconstruction of Discrete Sets from Three or More X-Rays. 199-210
  
• Donatella Merlini, Renzo Sprugnoli, M. Cecilia Verri:
  Modified Binary Searching for Static Tables. 211-225
  
• Sebastiano Battiato, Domenico Cantone, Dario Catalano, Gianluca Cincotti, Micha Hofri:
  An Efficient Algorithm for the Approximate Median Selection Problem. 226-238
  
• Emanuele Covino, Giovanni Pani, Salvatore Caporaso:
  Extending the Implicit Computational Complexity Approach to the Sub-elementary Time-Space Classes. 239-252
  
• Sabine Hanke, Eljas Soisalon-Soininen:
  Group Updates for Red-Black Trees. 253-262
  
• Irit Dinur:
  Approximating SVP_infty to within Almost-Polynomial Factors Is NP-Hard. 263-276
  
• Kathleen Steinhöfel, Andreas Alexander Albrecht, Chak-Kuen Wong:
  Convergence Analysis of Simulated Annealing-Based Algorithms Solving Flow Shop Scheduling Problems. 277-290
  
• Valentin E. Brimkov, Bruno Codenotti, Valentino Crespi, Mauro Leoncini:
  On the Lovász Number of Certain Circulant Graphs. 291-305
  
• Yusuke Shibata, Takuya Kida, Shuichi Fukamachi, Masayuki Takeda, Ayumi Shinohara, Takeshi Shinohara, Setsuo Arikawa:
  Speeding Up Pattern Matching by Text Compression. 306-315