ALGO 2004 Main page

ALGO 2004: Detailed schedule

Although the schedule is now complete, it is still subject to minor changes.

Monday, 13 September 2004

15:00: ALGO registration desk opens at Radisson SAS Royal Hotel.

19:00: Welcoming reception by the City of Bergen in Håkon's Hall.

Tuesday, 14 September 2004

8:30 Opening speeches
9:00 Plenary invited speech: Monika Henzinger

Algorithmic Aspects of Web Search Engines

9:50 Short break
10:00 Fast sparse matrix multiplication
Raphael Yuster, Uri Zwick
Solving Geometric Covering Problems by Data Reduction
Steffen Mecke, Dorothea Wagner
Reversing Gene Erosion - Reconstructing Ancestral Bacterial Genomes from Gene-Content and Gene Order Data
Joel V. Earnest-DeYoung, Emmanuelle Lerat, Bernard M.E. Moret
WAOA invited speech:

Yossi Azar

Online packet switching - techniques and algorithms

IWPEC invited speech:

Mike Langston

Practical FPT Implementations and Applications

10:25 Maximum Matching in Planar Graphs via Gaussian Elimination
Marcin Mucha, Piotr Sankowski
An Experimental Study of Random Knapsack Problems
Rene Beier, Berthold Voecking
Reconstructing Ancestral Gene Orders Using Conserved Intervals
Anne Bergeron, Mathieu Blanchette, Annie Chateau, Cedric Chauve
10:50 Coffee break
11:15 Approximate Unions of Lines and Minkowski Sums
Marc van Kreveld, A. Frank van der Stappen
Swap and Mismatch Edit Distance
Amihood Amir, Estrella Eisenberg, Ely Porat
Sorting By Reversals with Common Intervals
Figeac Martin, Varre Jean-Stephane
Improved bounds for sum multicoloring and weighted completion time of dependent jobs
Rajiv Gandhi, Magnus Halldorsson, Guy Kortsarz, Hadas Shachnai
Computing Small Search Numbers in Linear Time
Hans Bodlaender, Dimitrios Thilikos
11:40 Efficient Tradeoff Schemes in Data Structures for Querying Moving Objects
Pankaj K. Agarwal, Lars Arge, Jeff Erickson, Hai Yu
Approximate Parameterized Matching
Carmit Hazay, Moshe Lewenstein, Dina Sokol
A Polynomial-Time Algorithm for the Matching of Crossing Contact-Map Patterns
Jens Gramm
Minimum Sum Multicoloring on the Edges of Planar Graphs and Partial k-trees
Daniel Marx
Online Problems, Pathwidth, and Persistence
Rodney Downey, Catherine McCartin
12:05 Optimal External-Memory Planar Point Enclosure
Lars Arge, Vasilis Samoladas, Ke Yi
An Algorithm for Computing DNA Walks
Ankur Bhargava, S. Rao Kosaraju
A 1.5-Approximation Algorithm for Sorting by Transpositions and Transreversals
Tzvika Hartman, Roded Sharan
Strong Colorings of Hypergraphs
Geir Agnarsson, Magnus Halldorsson
Parameterized Graph Separation Problems
Daniel Marx
12:30 Lunch
14:00 Direct Routing: Algorithms and Complexity
Costas Busch, Malik Magdon-Ismail, Marios Mavronicolas, Paul Spirakis
Labeling Smart Dust
Vikas Bansal, Friedhelm Meyer auf der Heide, Christian Sohler
Algorithms for finding maximal-scoring segment sets
Miklos Csuros
Ordering-Preserving Transformations and Greedy-like Algorithms
Spyros Angelopoulos
Compatibility of Unrooted Phylogenetic Trees is FPT
David Bryant, Jens Lagergren
14:25 Path Decomposition under a New Cost Measure with Applications to Optical Network Design
Elliot Anshelevich, Lisa Zhang
On Rectangular Cartograms
Marc van Kreveld, Bettina Speckmann
Gapped Local Similarity Search with Provable Guarantees
Manikandan Narayanan, Richard Karp
Approximation Schemes for Deal Splitting and Covering Integer Programs with Multiplicity Constraints
H. Shachnai, O. Shmueli, R. Sayegh
Perfect Path Phylogeny Haplotyping with Missing Data is Fixed-Parameter Tractable
Jens Gramm, Till Nierhoff, Till Tantau
14:50 Time Dependent Multi Scheduling of Multicast
Rami Cohen, Dror Rawitz, Danny Raz
A Straight Skeleton Approximating the Medial Axis
Mirela Tanase, Remco C. Veltkamp
Monotone Scoring of Patterns with Mismatches
Alberto Apostolico, Cinzia Pizzi
Universal Bufferless Routing
Costas Busch, Malik Magdon-Ismail, Marios Mavronicolas
Parameterized Enumeration, Transversals, and Phylogeny Reconstruction
Peter Damaschke
15:15 Coffee break
15:45 Dynamic Shannon Coding
Travis Gagie
Stable Minimum Storage Merging by Symmetric Comparisons
Pok-Son Kim, Arne Kutzner
Suboptimal local alignments across multiple scoring schemes
Morris Michael, Christoph Dieterich, Jens Stoye
A 5/4-approximation algorithm for biconnecting a graph with a given Hamiltonian path
Davide Bilo, Guido Proietti
Refined Memorisation for Vertex Cover
L. Sunil Chandran, Fabrizio Grandoni
16:10 On the Stability of Multiple Partner Stable Marriages with Ties
Marun S. Malhotra
Beyond Optimal Play in Two-Person-Zerosum Games
Ulf Lorenz
A faster reliable algorithm to estimate the p-value of the multinomial llr statistic
Uri Keich, Niranjan Nagarajan
Approximating directed multicuts
Yana Kortsarts, Guy Kortsarz, Zeev Nutov
Greedy Localization, Iterative Compression and Modeled Crown Reductions: New FPT Techniques, an Improved Algorithm for SET SPLITTING and a Novel 2k Kernelization for VERTEX COVER
Frank Dehne, Michael Fellows, Frances Rosamond, Peter Shaw
16:35 Short break  
16:45 Business meeting

Wednesday, 15 September 2004

9:00 Plenary invited speech: Mike Fellows

A Survey of FPT Algorithm Design Techniques with an Emphasis on Recent Advances and Connections to Practical Computing

9:50 Short break
10:00   On Dynamic Shortest Paths Problems
Liam Roditty, Uri Zwick
Adding Hidden Nodes to Gene Networks.
Tamir Tuller, Benny Chor
Priority Algorithms for Graph Optimization Problems
A. Borodin, J. Boyar, K. S. Larsen
IWPEC invited speech:

Gerhard Woeginger

Space and time complexity of exact algorithms: Some open problems

10:25 Convergence Properties of the Gravitational Algorithm in Asynchronous Robot Systems
Reuven Cohen, David Peleg
Non-additive Shortest Paths
George Tsaggouris, Christos Zaroliagis
Joint Analysis of DNA Copy Numbers and Expression Levels
Doron Lipson, Amir Ben-Dor, Elinor Dehan, Zohar Yakhini
Online bin packing with resource augmentation
Leah Epstein, Rob van Stee
10:50 Coffee break
11:15 On the Evolution of Selfish Routing
Simon Fischer, Berthold Voecking
Multi-word Atomic Read/Write Registers on Multiprocessor Systems
Andreas Larsson, Anders Gidenstam, Phuong H. Ha, Marina Papatriantafilou, Philippas Tsigas
Searching for Regulatory Elements of Alternative Splicing Events Using Phylogenetic Footprinting
Daichi Shigemizu, Osamu Maruyama
This side up!
Leah Epstein, Rob van Stee
On Miniaturized Problems in Parameterized Complexity Theory
Yijia Chen, Joerg Flum
11:40 Fisher Equilibrium Price with a Class of Concave Utility Functions
Ning Chen, Xiaotie Deng, Xiaoming Sun, Andrew Chi-Chih Yao
Data Migration on Parallel Disks Leana Golubchik, Samir Khuller, Yoo-Ah Kim,
Svetlana Shargorodskaya, Yung-Chun (Justin) Wan
Supervised learning-aided optimization of expert-driven functional protein sequence annotation
Lev Soinov, Alexander Kanapin, Misha Kapushesky
Approximation Algorithms for Spreading Points
Sergio Cabello
Bounded Fixed-Parameter Tractability: The Case 2poly(k)
Mark Weyer
12:05   Efficient IP Table Lookup via Adaptive Stratified Trees with Selective Reconstructions
Marco Pellegrini, Giordano Fusco
Multiple vector seeds for protein alignment
Daniel Brown
Submodular Integer Cover and its Application to Production Planning
T. Fujito, T. Yabuta
Simplifying the Weft Hierarchy
Jonathan Buss, Tarique Islam
12:30 Lunch
14:00 Maximizing Throughput in Multi-Queue Switches
Yossi Azar, Arik Litichevskey
Finding Dominators in Practice
Loukas Georgiadis, Renato F. Werneck, Robert E. Tarjan, Spyridon Triantafyllis, David August
Solving the protein threading problem by lagrangian relaxation
Stefan Balev
Joint Base Station Scheduling
T. Erlebach, R. Jacob, M. Mihalak, M. Nunkesser, G. Szabo, P. Widmayer
Moving Policies in Cyclic Assembly-Line Scheduling
Matthias Mueller-Hannemann, Karsten Weihe
14:25 Improved Online Algorithms for Buffer Management in QoS Switches
Marek Chrobak, Wojciech Jawor, Jiri Sgall, Tomas Tichy
Construction of Minimum-Weight Spanners
Mikkel Sigurd, Martin Zachariasen
Protein-Protein Interfaces: Recognition of Similar Spatial and Chemical Organizations
Alexandra Shulman-Peleg, Shira Mintz, Ruth Nussinov, Haim Wolfson
Deterministic Monotone Algortihms for Scheduling on Related Machines
P. Ambrosio, V. Auletta
Chordless Paths Through Three Vertices
Michael Hoffmann, Robert Haas
14:50 An Improved Algorithm for CIOQ Switches
Y. Azar, Y. Richter
Contraction and Treewidth Lower Bounds
Hans L. Bodlaender, Arie M. C. A. Koster, Thomas Wolle
ATDD: An Algorithmic Tool for Domain Discovery in Protein Sequences
Stanislav Angelov, Sanjeev Khanna, Li Li, Fernando Pereira
Stochastic Online Scheduling on Parallel Machines
N. Megow, M. Uetz, T. Vredeveld
Parameterized Coloring Problems on Chordal Graphs
Daniel Marx
15:15 Coffee break
15:45 Lower Bounds for Embedding into Distributions over Excluded Minor Graph Families
Douglas E. Carroll, Ashish Goel
An Inductive Construction for Plane Laman Graphs via Vertex Splitting
Zsolt Fekete, Tibor Jordan, Walter Whiteley
Local Search Heuristic for Rigid Protein Docking
Vicky Choi, Pankaj Agarwal, Herbert Edelsbrunner, Johannes Rudolph
More Powerful and Simpler Cost-Sharing Methods
P. Penna, C. Ventre
On Decidability of MSO Theories of Representable Matroids
Petr Hlineny, Detlef Seese
16:10 Graph Decomposition Lemmas and Their Role in Metric Embedding Methods
Yair Bartal
Fast 3-coloring Triangle-Free Planar Graphs
Lukasz Kowalik
Translation Initiation Sites Prediction with mixture Gaussian models
Guoliang Li, Tze-Yun Leong, Louxin Zhang
Pricing Network Edges to Cross a River
A. Grigoriev, S. van Hoesel, A. F. van der Kraaij, M. Uetz, M. Bouhtou
On Finding Short Resolution Refutations and Small Unsatisfiable Subsets
Michael Fellows, Stefan Szeider, Graham Wrightson
16:35   Short break
16:45 Business meeting
19:00 Conference dinner
(funicular departure 18:30)

Thursday, 16 September 2004

9:00 Plenary invited speech: Marie-France Sagot

Some questions around genome rearrangements

9:50 Short break
10:00 Hardness and Approximation Results for Packing Steiner Trees
Joseph Cheriyan, Mohammad R. Salavatipour
Extreme Points under Random Noise
Valentina Damerow, Christian Sohler
Linear Reduction for Haplotype Inference
Jingwu He, Alex Zelikovsky
WAOA invited speech:

Klaus Jansen

Approximation algorithms for mixed fractional packing and covering problems

A Structural View on Parameterizing Problems: Distance from Triviality
Jiong Guo, Falk Hüffner, Rolf Niedermeier
10:25 Approximation Algorithms for Quickest Spanning Tree Problems
Refael Hassin, Asaf Levin
Seeking a Vertex of the Planar Matching Polytope in NC
Raghav Kulkarni, Meena Mahajan
A new integer programming formulation for the pure parsimony problem in haplotype analysis
Daniel Brown, Ian Harrower
The Minimum Weight Triangulation Problem with Few Inner Points
Michael Hoffmann, Yoshio Okamoto
10:50 Coffee break
11:15 Fractional Covering with Upper Bounds on the Variables: Solving LPs with Negative Entries
Naveen Garg, Rohit Khandekar
On Adaptive Integer Sorting
Anna Pagh, Rasmus Pagh, Mikkel Thorup
Fast Hare: a Fast Heuristic for Single Individual SNP Haplotype Reconstruction
Alessandro Panconesi, Mauro Sozio
A PTAS for Delay Minimization in Establishing Wireless Conference Calls
Leah Epstein, Asaf Levin
Looking at the Stars
Elena Prieto, Christian Sloper
11:40 Flows on Few Paths: Algorithms and Lower Bounds
Maren Martens, Martin Skutella
The Average Case Analysis of Partition Sorts
Richard Cole, David C. Kandathil
Approximation Algorithms for the Selection of Robust Tag SNPs
Yao-Ting Huang, Kui Zhang, Ting Chen, Kun-Mao Chao
Off-line Admission Control for Advance Reservations in Star Networks
U. Adamy, T. Erlebach, D. Mitsche, I. Schurr, B. Speckmann, E. Welzl
Smaller Kernels for Hitting Set Problems of Constant Arity
Naomi Nishimura, Prabhakar Ragde, Dimitrios Thilikos
12:05 Incremental Algorithms for Facility Location and k-Median
Dimitris Fotakis
Super Scalar Sample Sort
Peter Sanders, Sebastian Winkel
The Minisatellite Transformation Problem Revisited: A Run Length Encoded Approach
Behshad Behzadi, Jean-Marc Steyaert
Better bounds for minimizing SONET ADMs
Leah Epstein, Asaf Levin
Packing Edge Disjoint Triangles: A Parameterized View
Luke Mathieson, Elena Prieto, Peter Shaw
12:30 Lunch
14:00 Code Flexibility and Program Efficiency by Genericity: Improving Cgal's Arrangements
Efi Fogel, Ron Wein, Dan Halperin
Modeling Locality: A Probabilistic Analysis of LRU and FWF
Luca Becchetti
A Faster and More Space-Efficient Algorithm for Inferring Arc-Annotations of RNA Sequences through Alignment
Jesper Jansson, See-Kiong Ng, Wing-Kin Sung, Willy Hugo
  A Direct Algorithm for the Parameterized Face Cover Problem
Faisal Abu-Khzam, Mike Langston
14:25 Classroom Examples of Robustness Problems in Geometric Computations
Lutz Kettner, Kurt Mehlhorn, Sylvain Pion, Stefan Schirra, Chee Yap
On Variable-Sized Multidimensional Packing
Leah Epstein, Rob van Stee
New Algorithms for Multiple DNA Sequence Alignment
Daniel G. Brown, Alexander K. Hudek
Parameterized Algorithms for Feedback Vertex Set
Iyad Kanj, Michael Pelsmajer, Marcus Schaefer
14:50 Comparing real algebraic numbers of small degree
Ioannis Z. Emiris, Elias Tsigaridas
Competitive Online Approximation of the Optimal Search Ratio
Rudolf Fleischer, Tom Kamphans, Rolf Klein, Elmar Langetepe, Gerhard Trippen
Chaining algorithms for alignment of draft sequence
Michael Brudno, Mukund Sundararajanan, Serafim Batzoglou
Improved Parameterized Algorithms for Feedback Set Problems in Weighted Tournaments
Venkatesh Raman, Saket Saurabh
15:15 Coffee break
15:45 Plenary invited speech: Leo Kroon

Railway Optimization: An overview

16:35 Short break
16:40   Business meeting   Automated Proofs of Upper Bounds on the Running Time of Splitting Algorithms
Sergey Fedin, Alexander Kulikov

Friday, 17 September 2004

9:00 Plenary invited speech: David Eppstein

Quasiconvex Programming

9:50 Short break
10:00 Uniform Algorithms for Deterministic Construction of Efficient Dictionaries
Milan Ruzic
An Approximation Algorithm for Maximum Triangle Packing
Refael Hassin, Shlomi Rubinstein
Online Consensus and Agreement of Phylogenetic Trees
Tanya Y. Berger-Wolf
Platform Assignment
Sabine Cornelsen, Gabriele Di Stefano
10:25 Fast Multipoint Evaluation of Bivariate Polynomials
Michael Nüsken, Martin Ziegler
Approximation Hardness of Dominating Set Problems
Miroslav Chlebik, Janka Chlebikova
Relation of residues in the variable region of 16S rDNA sequences and their relevance to genus-specificity
Maciej Liskiewicz, Hemant Purohit, Dhananjay Raje
Rotation Planning of locomotives and carriage groups with shared capacities
Taieb Mellouli, Leena Suhl
10:50 Coffee break
11:15 Load Balancing of Indivisible Unit Size Tokens in Dynamic and Heterogeneous Network
Robert Elsaesser, Burkhard Monien, Stefan Schamberger
Faster Fixed-Parameter Tractable Algorithms for Matching and Packing problems
M.R. Fellows, C. Knauer, N. Nishimura, P. Ragde, F. Rosamond, U. Stege, D.M. Thilikos, S. Whitesides
Topological Rearrangements and Local Search Method for Tandem Duplication Trees
Denis Bertrand, Olivier Gascuel
Finding All Attractive Train Connections by Multi-Criteria Pareto Search
Matthias Müller-Hannemann, Mathias Schnee
11:40 Radio Network Clustering from Scratch
Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer
A Parameterized Algorithm for Upward Planarity Testing
Hubert Chan
Phylogenetic Super-Networks from Partial Trees
Daniel Huson, Tobias Dezulian, Tobias Klöpper, Mike Steel
The Railway Traveling Salesman Problem
Georgia Hadjicharalambous, Petrica Pop, Evangelia Pyrga, George Tsaggouris, Christos Zaroliagis
12:05 Load Balancing in Hypercubic Distributed Hash Tables with Heterogeneous Processors
Junning Liu, Micah Adler
Fixed Parameter Algorithms for Counting and Deciding Bounded Restrictive List H-Colorings
Josep Diaz, Maria Serna, Dimitrios M. Thilikos
Phylogeny by Hybridization
Stanislav Angelov, Boulos Harb, Sampath Kannan, Sanjeev Khanna, Junhyong Kim, Li-San Wang
An integrated Methodology for the rapid transit network design
Gilbert Laporte, Alfredo Marin, Juan Antonio Mesa, Francisco Ortega
12:30 Lunch
14:00 A Fast Distributed Algorithm for Approximating the Maximum Matching
Andrzej Czygrinow, Michal Hanckowiak, Edyta Szymanska
Approximation of Rectangle Stabbing and Interval Stabbing problems
Sofia Kovaleva, Frits Spieksma
Novel tree edit operations for RNA secondary structure comparison
Julien Allali, Marie-France Sagot
Fare integration in regional transit services
Domenico Gattuso, Giuseppe Musolino
14:25 Algorithms for Generating Minimal Blockers of Perfect Matchings in Bipartite Graphs and Related Problems
E. Boros, E. Elbassioni, V. Gurvich
Tiling a Polygon with Two Kinds of Rectangles
Eric Remila
The Most Probable Labeling Problem in HMMs and Its Application to Bioinformatics
Brona Brejova, Daniel G. Brown, Tomas Vinar
Intelligent Train scheduling on a High-Loaded Railway Network
Antonio Lova, Pilar Tormos, Federico Barber, Laura Ingolotti, Miguel A. Salido, Montserrat Abril
14:50 Equivalence of Search Capability among Mobile Guards with Various Visibilities
Jae-Ha Lee, Sang-Min Park, Kyung-Yong Chwa
  Integrating Sample-driven and Pattern-driven Approaches in Motif Finding
Sing-Hoi Sze, Songjian Lu, Jianer Chen
On-Line Delay Management on a Single Transit Line
Michael Gatto, Riko Jacob, Leon Peeters, Peter Widmayer
15:15 Coffee break
15:45   Finding Optimal Pairs of Patterns
Hideo Bannai, Heikki Hyyro, Ayumi Shinohara, Masayuki Takeda, Kenta Nakai, Satoru Miyano
An estimate of the punctuality benefits of automatic operational train sequencing
Maarten Bartholomeus, Rien Gouweloos
16:10 Finding missing patterns
Shunsuke Inenaga, Teemu Kivioja, Veli Mäkinen
Business meeting

ALGO 2004 Main page

This page is maintained by Eivind Coward. Last modified: 15 Sep 2004