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