Program Schedule

ALGO 2001

BRICS, University of Aarhus, Denmark, August 28-31, 2001

ALGO 2002
September 16-21
Rome ``La Sapienza''
ALGO 2001
-Online Registration (closed)
-Registration fees
-Travel and tourist Information
-Author index
ESA 2001
-Accepted papers
-Call for papers
WAE 2001
-Accepted papers
-Call for papers
WABI 2001
-Accepted papers
-Accepted posters
-Call for papers
-Call for posters
-Accepted papers
-Call for papers
[ Site map ]

[ ps | pdf ]


August 27
August 28
August 29
August 30
August 31
Registration Registration  
Invited speaker Invited speaker Invited speaker Invited speaker ESA 16 WABI 9
Coffee break ESA 1 WAE 1 ESA 5 WAE 3 ESA 9 WAE 5 WABI P1 ESA 13 WABI 7
ARACNE 1Coffee break Coffee break Coffee break Coffee break
Lunch Lunch Lunch Lunch Lunch
Invited speaker Invited speaker Invited speaker Invited speaker ESA 15  
Coffee break ESA 3 WABI 1 ESA 7 WABI 3 ESA 11 WABI 5  
ARACNE 2 Coffee break Coffee break Coffee break
Registration   Concert hall reception Business meeting
Conference dinner


Monday August 27
08:00-09:00 RegistrationIn front of Auditorium F
09:00-09:05 ARACNE 2001 opening remarksAuditorium F
09:05-09:55Invited presentation: Multiple-Choice Algorithms
Berthold Vöcking
Auditorium F
09:55-10:20 Coffee break
ARACNE Session 1
10:20 Dynamic Bandwidth Allocation: Lower Bounds on Latency for a Class of Randomized Single Servers
Sotiris Nikoletseas and Paul Spirakis
10:45 The Cost of Lack of Coordination in Distributed Network Routing
Marios Mavronicolas, Antonis Mouskos, and Paul Spirakis
11:10 Efficient Management of Transient Station Failures in Linear Radio Communication Networks with Bases
Carlo Gaibisso, Guido Proietti, and Richard Tan
11:35 Optimal Gossiping on CCCs of Even Dimension
Jop F. Sibeyn and Michal Soch
Auditorium F
12:00-14:15 Lunch
14:15-15:05Invited presentation: Non-clairvoyant scheduling to minimize the average flow time
Stefano Leonardi
Auditorium F
15:05-15:30 Coffee break
ARACNE Session 2
15:30 Hamiltonian cycles in faulty random geometric networks
Jordi Petit
15:55 Wavelength assignment problem in all-optical rings revisited
Luciano Margara
16:20 Better Alternatives to OSPF Routing
Jessica H. Fong, Anna C. Gilbert, Sampath Kannan, and Martin J. Strauss
Auditorium F
17:30-21:00 Registration and GettogetherCoffee lounge, Building 540
Tuesday August 28
08:00-09:00 RegistrationIn front of Auditorium F
09:00-09:05 WelcomeAuditorium E
09:05-10:00Invited presentation: External memory data structures
Lars Arge
Auditorium E
Concurrent sessions
ESA Session 1: Caching and Prefetching
10:00 Strongly Competitive Algorithms for Caching with Pipelined Prefetching
Alexander Gaysinsky, Alon Itai, and Hadas Shachnai
10:25 Duality Between Prefetching and Queued Writing with Parallel Disks
David A. Hutchinson, Peter Sanders, and Jeffrey Scott Vitter
Auditorium F
WAE Session 1
10:00 Compact DFA Representation for Fast Regular Expression Search
Gonzalo Navarro and Mathieu Raffinot
10:25 The max-shift algorithm for approximate string matching - cancelled
Costas S. Iliopoulos, Laurent Mouchard, and Yoan J. Pinzon
Auditorium G1
10:50-11:15 Coffee break
Concurrent sessions
ESA Session 2: Online Algorithms
11:15 Online Bin-Coloring
Sven Oliver Krumke, Willem de Paepe, Joerg Rambau, and Leen Stougie
11:40 A General Decomposition Theorem for the k-Server Problem
Steve Seiden
12:05 Buying a constant competitive ratio for paging
J. Csirik, C. Imreh, J. Noga, S. Seiden, and G.J. Woeginger
Auditorium F
WAE Session 2
11:15 Fractal Matrix Multiplication: a Case Study on Portability of Cache Performance
Gianfranco Bilardi, Paolo D'Alberto, and Alexandru Nicolau
11:40 Experiences with the design and implementation of space-efficient deques
Jyrki Katajainen and Bjarke Buur Mortensen
12:05 Designing and implementing a general purpose halfedge data structure
Hervé Brönnimann
Auditorium G1
12:30-14:00 Lunch
14:00-15:00Invited presentation: Algorithms for Statistical Multiple Alignment
Jotun Hein
Auditorium E
Concurrent sessions
ESA Session 3: Data Structures I
15:00 Simple minimal perfect hashing in less space
Martin Dietzfelbinger and Torben Hagerup
15:25 Cuckoo Hashing
Rasmus Pagh and Flemming Friche Rodler
Auditorium F
WABI Session 1: Alignment
15:00 An improved model for statistical alignment
I. Miklos and Z. Toroczkai
15:25 Improving profile-profile alignments via log average scoring
N. von Oehsen and R. Zimmer
Auditorium G1
15:50-16:15 Coffee break
Concurrent sessions
ESA Session 4: Optimization and Approximation
16:15 Coupling Variable Fixing Algorithms for the Automatic Recording Problem
Meinolf Sellmann and Torsten Fahle
16:40 Approximation algorithms for scheduling malleable tasks under precedence constraints
R. Lepere, D. Trystram, and G.J. Woeginger
17:05 On the Approximability of the Minimum Test Collection Problem
B.V. Halldorsson, M.M. Halldorsson, and R. Ravi
Auditorium F
WABI Session 2: Genetic mapping
16:15 False positives in genomic map assembly and sequence validation
T. Anantharaman and B. Mishra
16:40 Boosting EM for radiation hybrid and genetic mapping - cancelled
T. Schiex, P. Chabrier, M. Bouchez, and D. Milan
16:40 Comparing assemblies using fragments and mate-pairs
D.H. Huson, A.L. Halpern, Z. Lai, E.W. Myers, K. Reinert, and G.G. Sutton
17:05 Placing probes along the genome using pairwise distance data
W. Casey, B. Mishra, and M. Wigler
Auditorium G1
Wednesday August 29
09:00-10:00Invited presentation: Some algorithmic problems in large networks
Susanne Albers
Auditorium E
Concurrent sessions
ESA Session 5: Sequences
10:00 Finding approximate repetitions under Hamming distance
Roman Kolpakov and Gregory Kucherov
10:25 SNPs Problems, Complexity and Algorithms
Giuseppe Lancia, Vineet Bafna, Sorin Istrail, Ross Lippert, and Russell Schwartz
Auditorium F
WAE Session 3
10:00 Optimised Predecessor Data Structures for Internal Memory
Naila Rahman, Richard Cole, and Rajeev Raman
10:25 An Adaptable and Extensible Geometry Kernel
Susan Hert, Michael Hoffmann, Lutz Kettner, Sylvain Pion, and Michael Seel
Auditorium G1
10:50-11:15 Coffee break
Concurrent sessions
ESA Session 6: Scheduling
11:15 A FPTAS for approximating the unrelated parallel machines scheduling problem with costs
E. Angel, E. Bampis, and A. Kononov
11:40 Grouping techniques for scheduling problems: simpler and faster
Aleksei V. Fishkin, Klaus Jansen, and Monaldo Mastrolilli
12:05 A 2-approximation algorithm for the multi-vehicle scheduling problem on a path with release and handling times
Y. Karuno and H. Nagamochi
Auditorium F
WAE Session 4
11:15 Efficient Resource Allocation with Noisy Functions
Arne Andersson, Per Carlsson, and Fredrik Ygge
11:40 Improving the efficiency of Branch and Bound Algortihms for the Simple Plant Location Problem
Boris Goldengorin, Diptesh Ghosh, and Gerard Sierksma
12:05 Exploiting Partial Knowledge of Satisfying Assignments
Kazuo Iwama and Suguru Tamaki
Auditorium G1
12:30-14:00 Lunch
14:00-15:00Invited presentation: Exact and approximate distances in graphs
Uri Zwick
Auditorium E
Concurrent sessions
ESA Session 7: Shortest Paths
15:00 A Simple Shortest Path Algorithm with Linear Average Time
Andrew V. Goldberg
15:25 A Heuristic for Dijkstra's Algorithm with Many Targets and its Use in Weighted Matching Algorithms
Kurt Mehlhorn and Guido Schaefer
Auditorium F
WABI Session 3: Statiscal models
15:00 Comparing stochastic models
A. Jagota, R.B. Lyngso, and C.N.S. Pedersen
15:25 Assessing the statistical significance of overrepresented oligonucleotides
A. Denise, M. Regnier, and M. Vandenbogaert
Auditorium G1
15:50-16:15 Coffee break
Concurrent sessions
ESA Session 8: Geometry I
16:15 A Separation Bound for Real Algebraic Expressions
Christoph Burnikel, Stefan Funke, Kurt Mehlhorn, Stefan Schirra, and Susanne Schmitt
16:40 Property Testing with Geometric Queries
Artur Czumaj and Christian Sohler
17:05 Smallest Color-Spanning Objects
Manuel Abellanas, Ferran Hurtado, Christian Icking, Rolf Klein, Elmar Langetepe, Lihong Ma, Belen Palop, and Vera Sacristan
Auditorium F
WABI Session 4: Protein structure
16:15 Pattern matching and pattern discovery algorithms for protein topologies
J. Viksna and D. Gilbert
16:40 Computing linking numbers of a filtration
H. Edelsbrunner and A. Zomorodian
17:05 Side chain-positioning as an integer programming problem
O. Eriksson, Y. Zhou, and A. Elofsson
Auditorium G1
18:30 Concert hall reception
Thursday August 30
09:00-10:00Invited presentation: Bio-Geometric Modeling
Herbert Edelsbrunner
Auditorium E
Concurrent sessions
ESA Session 9: Data Structures II
10:00 Explicit Deterministic Constructions for Membership in the Bitprobe Model
Jaikumar Radhakrishnan, Venkatesh Raman, and S. Srinivasa Rao
10:25 Lossy Dictionaries
Rasmus Pagh and Flemming Friche Rodler
Auditorium F
WAE Session 5
10:00 Using PRAM Algorithms on a Uniform-Memory-Access Shared-Memory Architecture
David A. Bader, Ajith K. Illendula, and Bernard M.E. Moret
10:25 An Experimental Study of Data Migration Algorithms
Eric Anderson, Joe Hall, Jason D. Hartline, Michael Hobbs, Anna Karlin, Jared Saia, Ram Swaminathan, and John Wilkes
Auditorium G1
WABI Poster Session 1
Auditorium G2
10:50-11:15 Coffee break
Concurrent sessions
ESA Session 10: Geometry II
11:15 Splitting a Delaunay triangulation in linear time
Bernard Chazelle, Olivier Devillers, Ferran Hurtado, Merce Mora, Vera Sacristan, and Monique Teillaud
11:40 A fast algorithm for approximating the detour of a polygonal chain
Annette Ebbers-Baumann, Rolf Klein, Elmar Langetepe, and Andrzej Lingas
12:05 An Approximation Algorithm for Minimum Convex Cover with Logarithmic Performance Guarantee
Stephan Eidenbenz and Peter Widmayer
Auditorium F
WAE Session 6
11:15 An Experimental Study of Basic Communication Protocols in Ad-hoc Mobile Networks
Ioannis Chatzigiannakis, Sotiris Nikoletseas, Nearchos Paspallis, Paul Spirakis, and Christos Zaroliagis
11:40 Experimental Analysis of Algorithms for Bilateral-Contract Clearing Mechanisms Arising in Deregulated Power Industry
Chris Barrett, Doug Cook, Vance Faber, Gregory Hicks, Achla Marathe, Madhav Marathe, Aravind Srinivasan, Yoram J. Sussmann, and Heidi Thornquist
12:05 Pareto Shortest Paths is Often Feasible in Practice
Matthias Mueller-Hannemann and Karsten Weihe
Auditorium G1
WABI Poster Session 2
Auditorium G2
12:30-14:00 Lunch
14:00-15:00Invited presentation: Some algorithmic challenges in web search
Andrei Broder
Auditorium E
Concurrent sessions
ESA Session 11: Distributed Algorithms
15:00 Distributed O(Delta log n)-edge-coloring algorithm
A. Czygrinow, M. Hanckowiak, and M. Karonski
15:25 Modeling Replica Placement in a Distributed File System: Narrowing the Gap between Analysis and Simulation
John Douceur and Roger Wattenhofer
Auditorium F
WABI Session 5: Phylogeny
15:00 A chemical-distance-based test for positive Darwinian selection
T. Pupko, R. Sharan, M. Hasegawa, R. Shamir, and D. Graur
15:25 Finding the maximum compatible tree for a bounded number of trees with bounded degree is solvable in polynomial time
Ganeshkumar G. and T. Warnow
Auditorium G1
15:50-16:15 Coffee break
Concurrent sessions
ESA Session 12: Graph Algorithms
16:15 Computing Cycle Covers without Short Cycles
Markus Blaeser and Bodo Siebert
16:40 A polynomial time algorithm for the cutwidth of bounded degree graphs with small treewidth
Dimitrios M. Thilikos, Maria Serna, and Hans L. Bodlaender
17:05 Lower Bounds and Exact Algorithms for the Graph Partitioning Problem using Multicommodity Flows
Norbert Sensen
Auditorium F
WABI Session 6: Gene order
16:15 Experiments in computing sequences of reversals
A. Bergeron and F. Strasbourg
16:40 Improving the accuracy of evolutionary distances between genomes
L.-S. Wang
17:05 Finding an optimal inversion median: experimental results
A. Siepel and B.M.E. Moret
Auditorium G1
17:30-19:00 Business meetingAuditorium F
19:00 Conference dinner
Friday August 31
Concurrent sessions
ESA Session 16: Graphs
09:00 A General Model of Undirected Web Graphs
Colin Cooper and Alan Frieze
09:25 Packing Cycles and Cuts in Undirected Graphs
Alberto Caprara, Alessandro Panconesi, and Romeo Rizzi
Auditorium E
WABI Session 9: Sequence analysis
09:00 Determination of the binding amino acids based on random peptide array screening data
P.J. van der Veen, L.F.A. Wessels, J.W. Sloostra, R.H. Meloen, M.J.T. Reinders, and J. Hellendoorn
09:25 A simple hypergeometric approach for discovering putative transcription factor binding sites
Y. Barash, G. Bejerano, and N. Friedman
Auditorium G1
Concurrent sessions
ESA Session 13: Pricing
10:00 Fast Pricing of European Asian Options with Provable Accuracy: Single-stock and Basket Options
Karhan Akcoglu, Ming-Yang Kao, and Shuba V. Raghavan
10:25 Competitive Auctions for Multiple Digital Goods
Andrew V. Goldberg and Jason D. Hartline
Auditorium E
WABI Session 7: Phylogeny
10:00 MLMC trees and Hadamard conjugation
B. Chor, M. Hendy, and D. Penny
10:25 The performance of phylogenetic methods on trees of bounded diameter
L. Nakhleh, U. Roshan, K. St.John, J. Sun, and T. Warnow
Auditorium G1
10:50-11:15 Coffee break
Concurrent sessions
ESA Session 14: Broadcasting and Multicasting
11:15 Algorithms for Efficient Filtering in Content-Based Multicast
Stefan Langerman, Sachin Lodha, and Rahul Shah
11:40 Approximation Algorithms for Minimum-Time Broadcast under the Vertex-Disjoint Paths Mode
Pierre Fraigniaud
12:05 Round Robin is Optimal for Fault-Tolerant Broadcasting on Wireless Networks
A. Clementi, A. Monti, and R. Silvestri
Auditorium E
WABI Session 8: Gene order
11:15 (1+e)-approximation of sorting by reversals and transpositions
N. Eriksen
11:40 On the practical solution of the reversal median problem
A. Caprara
12:05 Algorithms for finding gene clusters
S. Heber and J. Stoye
Auditorium G1
12:30-14:00 Lunch
ESA Session 15: Graph Labeling and Graph Drawing
14:00 On-line and Off-line distance constrained labeling of disk graphs
Jiri Fiala, Aleksei V. Fishkin, and Fedor V. Fomin
14:25 Approximate Distance Labeling Schemes
C. Gavoille, M. Katz, N. Katz, C. Paul, and D. Peleg
14:50 On the Parameterized Complexity of Layered Graph Drawing
V. Dujmovic, M. Fellows, M. Hallett, M. Kitching, G. Liotta, C. McCartin, N. Nishimura, P. Ragde, F. Rosamond, M. Suderman, S. Whitesides, and D. R. Wood
15:15 Greedy algorithms for minimisation problems in random regular graphs
Michele Zito
Auditorium G1

Page maintained by Gerth Stølting Brodal