| Monday August 27 |
| 08:00-09:00 |
Registration | In front of Auditorium F |
| 09:00-09:05 |
ARACNE 2001 opening remarks | Auditorium F |
| 09:05-09:55 | Invited presentation: Multiple-Choice Algorithms
Berthold Vöcking | Auditorium F |
| 09:55-10:20 |
Coffee break |
| 10:20-12:00 | - 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:05 | Invited presentation: Non-clairvoyant scheduling to minimize the average flow time
Stefano Leonardi | Auditorium F |
| 15:05-15:30 |
Coffee break |
| 15:30-16:45 | - 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 Gettogether | Coffee lounge, Building 540 |
| Tuesday August 28 |
| 08:00-09:00 |
Registration | In front of Auditorium F |
| 09:00-09:05 |
Welcome | Auditorium E |
| 09:05-10:00 | Invited presentation: External memory data structures
Lars Arge | Auditorium E |
10:00-10:50
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 |
11:15-12:30
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:00 | Invited presentation: Algorithms for Statistical Multiple Alignment
Jotun Hein | Auditorium E |
15:00-15:50
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 |
16:15-17:30
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:00 | Invited presentation: Some algorithmic problems in large networks
Susanne Albers | Auditorium E |
10:00-10:50
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 |
11:15-12:30
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:00 | Invited presentation: Exact and approximate distances in graphs
Uri Zwick | Auditorium E |
15:00-15:50
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 |
16:15-17:30
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:00 | Invited presentation: Bio-Geometric Modeling
Herbert Edelsbrunner | Auditorium E |
10:00-10:50
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 |
11:15-12:30
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:00 | Invited presentation: Some algorithmic challenges in web search
Andrei Broder | Auditorium E |
15:00-15:50
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 |
16:15-17:30
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 meeting | Auditorium F |
| 19:00 |
Conference dinner |
| Friday August 31 |
09:00-09:50
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 |
10:00-10:50
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 |
11:15-12:30
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 |
| 14:00-15:40 | - 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 |