5th Conference on Algorithms and Complexity
May 28-30, 2003 Rome, Italy

Conference Program



Wednesday May 28

14:00 – 14:20    Conference Opening

14:20 – 15:20    Invited Talk   M.O. Rabin

15:20 – 15:50    Coffee Break
Session 1    (Geometric Algorithms)
15:50 – 16:15     Efficient Update Strategies for Geometric Computing with Uncertainty
                             
R. Bruce, M. Hoffmann, D. Krizanc, R. Raman
16:15 – 16:40    Maximizing the Guarded Boundary of an Art Gallery is APX-Complete
                             
E. Markou, S. Zachos, C. Fragoudakis
16:40 – 17:05     An Improved Algorithm for Point Set Pattern Matching under Rigid Motion
                       
      A. Bishnu, S. Das, S.C. Nandy, B.B. Bhattacharya

17:05 – 17:30    Coffee Break
Session 2    (On-line Algorithms)
17:30 – 17:55    Unlocking the Advantages of Dynamic Service Selection and Pricing
                           
B. Kalyanasundaram, M. Velauthapillai, J. Waclawsky
17:55 – 18:20    The Relative Worst Order Ratio for On-Line Algorithms
                           
J. Boyar, L. M. Favrholdt
18:20 – 18:45    On-Line Stream Merging, Max Span, and Min Coverage
                           
W-T. Chan, T-W. Lam, H-F. Ting, P. W. H. Wong


Thursday May 29

9:00 – 10:00      Invited Talk   C.E. Leiserson

10:00 – 10:30   
Coffee Break
Session 3    (Graph Algorithms)
10:30 – 10:55    Randomized Algorithms for Finding Small Weakly-Connected Dominating Sets of Regular Graphs
                            
W. Duckworth, B. Mans
10:55 – 11:20    Additive Spanners for k-Chordal Graphs
                            
V.D. Chepoi, F.F. Dragan, C. Yan
11:20 – 11:45    Graph-Modelled data Clustering: Exact Algorithms for Clique Generation
                            
J. Gramm, J. Guo, F. Hueffner, R. Niedermeier
11:45 – 12:10    Reconciling Gene Trees to a Species Tree
                            
P. Bonizzoni, G. Della Vedova, R. Dondi

12:10 – 13:40    Lunch

13:40 – 14:40    Invited Talk  
J.E. Savage

14:40 – 15:10    Coffee Break
Session 4    (Combinatorics)
15:10 – 15:35    Generating all forest extensions of a partially ordered set
                           
J.L. Szwarcfiter
15:35 – 15:50    Indexing Structures for Approximate String Matching
                           
A. Gabriele, F. Mignosi, A. Restivo, M. Sciortino
Social Event
Social Dinner

Friday May 30

9:00 – 10:00      Invited Talk   D. Peleg

10:00 – 10:30   
Coffee Break
Session 5    (Approximation Algorithms)
10:30 – 10:55    Approximation Harndess for Small Occurrence Instances of NP-Hard Problems
                           
M. Chlebik, J. Chlebikova
10:55 – 11:20    Fast Approximation of Minimum Multicast Congestion - Implementation versus Theory
                           
A. Baltz, A. Srivastav
11:20 – 11:45    Approximation of a retrieval problem for parallel disks
                           
J. Aerts, J. Korst, F. Spieksma
11:45 – 12:10    On K-Edge-Connectivity Problems with Sharpened Triangle Inequality
                           
H. Boeckenhauer, D. Bongartz, J. Hromkovic, R. Klasing, G. Proietti, S. Seibert, W. Unger

12:10 – 13:40    Lunch

13:40 – 14:40    Invited Talk  
L. Trevisan

14:40 – 15:10    Coffee Break
Session 6    (Computational Complexity)
15:10 – 15:35    The Complexity of Detecting Fixed-Density Clusters
                           
K. Holzapfel, S. Kosub, M. G. Maass, H. Taeubig
15:35 – 16:00    Nearly Bounded Error Probabilistic Sets
                           
T. Yamakami
16:00 – 16:25    Some Properties of MODm Circuits Computing Simple Functions
                           
K. Amano, A. Maruoka

16:25 – 16:50   
Coffee Break
Session 7    (Routing)
16:50 – 17:15    Parallel IP-Lookup Without Best Matching Prefix
                           
G. Bongiovanni, P. Penna
17:15 – 17:40    The Impact of Network Structure on the Stability of Greedy Protocols
                           
D. Koukopoulos, M. Mavronicolas, S. Nikoletseas, P. Spirakis
17:40 – 18:05    Improving Customer Proximity to Railway Stations
                           
E. Kranakis, P. Penna, K. Schlude, D.S. Taylor, P. Widmayer
18:05 – 18:30    Differential Approximation for some Routing Problems
                           
C. Bazgan, R. Hassin, J. Monnot