Workshop on Algorithms and Data Structures (WADS 2003) http://www.wads.org -- July 30 - August 1, 2003, Carleton Univ., Ottawa, Canada Conference Registration: http://www.wads.org (deadline: June 29) Hotel Registration: http://www.wads.org (deadline: June 29) ----------------------------------------------------------------- Schedule: July 29: Tutorial on Neural Networks (speaker: H.-G.Zimmermann, consult http://www.wads.org ) July 30 - August 1: WADS August 2: Workshop and Tutorial on Fixed Parameter Tractability (lead by Mike Fellows, consult http://www.wads.org ) ----------------------------------------------------------------- WADS Program ============ Tuesday July 29 --------------- 6:00 pm - 8:00 pm WADS registration and welcome reception, foyer Tory Building Wednesday July 30 ----------------- 9:30 - 10:30: Session 1: invited talk: Quantum Communication Complexity, by Gilles Brassard 10:30 - 11:00: coffee 11:00 - 12:00: Session 2A: Adapting (Pseudo)-Triangulations with a Near-Linear Number of Edge Flips, Oswin Aichholzer, Franz Aurenhammer, Hannes Krasser Shape Segmentation and Matching with Flow Discretization, Tamal Dey, Joachim Giesen, Samrat Goswami Session 2B: Phylogenetic Reconstruction from Gene Rearrangement Data with Unequal Gene Content, Jijun Tang, Bernard Moret Toward Optimal Motif Enumeration, Patricia Evans, Andrew Smith 1:30 - 3:00: Session 3A: Common-Deadline Lazy Bureaucrat Scheduling Problems, Behdad Esfahbo, Mohammad Ghodsi, Ali Sharifi Bandwidth-Constrained Allocation in Grid Computing, Anshul Kothari, Subhash Suri, Yunhong Zhou Algorithms and Approximation Schemes for Minimum Lateness/Tardiness Scheduling with Rejection, Sudipta Sengupta Session 3B: Fast Algorithms for a Class of Temporal Range Queries, Qingmin Shi, Joseph JaJa Distribution-Sensitive Binomial Queues, Amr Elmasry Optimal Worst-Case Operations for Implicit Cache-Oblivious Search Trees, Gianni Franceschini, Roberto Grossi 3:00 - 3:30: coffee 3:30 - 5:00: Session 4A: Extremal Configurations and Levels in Pseudoline Arrangements, Micha Sharir, Shakhar Smorodinsky Fast Relative Approximation of Potential Fields, Martin Ziegler The one-round Voronoi game replayed, Sandor Fekete, Henk Meijer Session 4B: Integrated Prefetching and Caching with Read and Write Requests, Susanne Albers, Markus Buttner On-Line Seat Reservations via Off-Line Seating Arrangements, Jens S. Frederiksen, Kim S. Larsen Routing and Call Control Algorithms for Ring Networks, R. Sai Anand, Thomas Erlebach 5:15 - 6:00: Special Presentation: Protecting your intellectual property, Wing T. Yan Thursday July 31 ---------------- 9:30 - 10:30: Session 5: invited talk: Algorithms and Models for Railway Optimization, by Dorothea Wagner 10:30 - 11:00: coffee 11:00 - 12:00: Session 6A: Approximation of Rectilinear Steiner Trees with Length Restrictions on Obstacles, Matthias Muller-Hannemann, Sven Peyer On the Hausdorff Voronoi diagram of point clusters in the plane, Evanthia Papadopoulou Session 6B: Cropping-Resilient Segmented Multiple Watermarking, Keith Frikken, Mikhail Atallah On Simultaneous Planar Graph Embeddings, P. Brass, E. Cenek, C. Duncan, A. Efrat, C. Erten, D. Ismailescu, S. Kobourov, A. Lubiw, J. Mitchell 1:30 - 2:30: Session 7: invited talk: Perturbation Models for Smoothed Analysis, by Daniel Spielman 2:30 - 3:00: coffee 3:00 - 5:00: Session 8A: Approximation Algorithm for Hotlink Assignments in Web Directories, Rachel Matichin, David Peleg Drawing Graphs with Large Vertices and Thick Edges, Gill Barequet, Michael T. Goodrich, Chris Riley Semi-Matchings for Bipartite Graphs and Load Balancing, Nicholas Harvey, Richard Ladner, Laszlo Lovasz, Tami Tamir The Traveling Salesman Problem for Cubic Graphs, David Eppstein Session 8B: Sorting circular permutations by reversal, Andrew Solomon, Paul Sutcliffe, Raymond Lister An improved bound on Boolean matrix multiplication for highly clustered data, Leszek Gasieniec, Andrzej Lingas Dynamic Text and Static Pattern Matching, Amihood Amir, Gad Landau, Moshe Lewenstein, Dina Sokol Real Two Dimensional Scaled Matching, Amihood Amir, Ayelet Butman, Moshe Lewenstein, Ely Porat Conference dinner at the Chateau Laurier, starting at 7pm. Friday August 1 --------------- 9:00 - 10:30: Session 9A: Proximity Structures for Geometric graphs, Sanjiv Kapoor, Xiang-Yang Li The Zigzag Path of a Pseudo-Triangulation, Oswin Aichholzer, Guenter Rote, Bettina Speckmann, Ileana Streinu Alternating Paths along Orthogonal Segmenta, Csaba Toth Session 9B: Improved Approximation Algorithms for the Quality of Service Steiner Tree Problem, Marek Karpinski, Ion Mandoiu, Alex Olshevsky, Alexander Zelikovsky Chips on Wafers, or Packing Rectangles into Grids, Mattias Andersson, Joachim Gudmundsson, Christos Levcopoulos A Model for Analyzing Black-Box Optimization, Pavel Sumazin, Vinhthuy Phan, Steve Skiena 10:30 - 11:00: coffee 11:00 - 12:30: Session 10A: Multi-way Space Partitioning Trees, Christian Duncan Output-Sensitive Algorithms for Computing Nearest-Neighbour Decision Boundaries, David Bremner, Erik Demaine, Jeff Erickson, John Iacono, Stefan Langerman, Pat Morin, Godfried Toussaint Significant-Presence Range Queries in Categorical Data, Mark de Berg, Herman J. Haverkort Session 10B: Either/Or: Using Vertex Cover Structure in designing FPT-algorithms - the case of k-Internal Spanning Tree, Elena Prieto, Christian Sloper Parameterized Complexity of Directed Feedback Set Problems in Tournaments, Venkatesh Raman, Saket Saurabh Compact Visibility Representation and Straight-Line Grid Embedding of Plane Graphs, Huaming Zhang, Xin He 2:00 - 3:00: Session 11: invited talk: New Directions and New Challenges in Algorithm Design and Complexity, Parameterized, by Michael Fellows 3:00 - 3:30: coffee