|
|
|
| SUNDAY 18:00 - 20:00 |
Registration at Hotel Tryp Bellver |
| MONDAY 12:30 - 13:30 |
Registration at Hotel Tryp Bellver |
| MONDAY 15:00 - 16:45 |
Registration at Hotel Tryp Bellver |
| 07:00 - 11:30 |
Eclipse observation (on your own) |
| 11:30 - 11:40 |
Opening |
| 11:40 - 12:30 |
Invited talk
Giuseppe F. Italiano
|
| 12:30 - 12:40 |
Short break |
| 12:40 - 13:25 |
Exploring an unknown graph efficiently
R. Fleischer and G. Trippen |
Heuristic improvements for computing max multicommodity flow and min multicut
G. Batra, N. Garg and G. Gupta |
Spectral Clustering Gene Ontology Terms to Group Genes by Function
N. Speer, C. Spieth and A. Zell |
| 13:05 - 13:30 |
Online Routing in Faulty Meshes with Sub-Linear Comparative Time and Traffic Ratio
S. Rührup and C. Schindelhauer |
Relax-and-cut for capacitated network design
G. Kliewer and L. Timajev |
Dynamic De-Novo Prediction of microRNAs Associated with Cell Conditions
C. Zilberstein and M. Ziv-Ukelson |
| 13:30 - 15:00 |
Lunch |
| 15:00 - 15:25 |
On the price of anarchy and stability of correlated equilibria of linear congestion games
G. Christodoulou and E. Koutsoupias |
Efficient Exact Algorithms on Planar Graphs: Exploiting Sphere Cut Branch Decompositions
F. Dorn, E. Penninkx, H. Bodlaender and F. Fomin |
Clustering Gene Expression Series with Prior Knowledge
L. Brehelin |
| 15:25 - 15:50 |
The Complexity of Games on Highly Regular Graphs (Extended Abstract)
K. Daskalakis and C. Papadimitriou |
An algorithm for the SAT problem for formulae of linear length
M. Wahlström |
A Linear Time Biclustering Algorithm for Time Series Gene Expression Data
S. Madeira and A. Oliveira |
| 15:50 - 16:15 |
Computing Equilibrium Prices: Does Theory Meet Practice?
B. Codenotti, B. McCune, R. Raman and K. Varadarajan |
Linear-Time Enumeration of Isolated Cliques
H. Ito, K. Iwama and T. Osumi |
Time-Window Analysis of Developmental Gene Expression Data with Multiple Genetic Backgrounds
T. Tuller, E. Oron, E. Makavy, D. Chamovitz and B. Chor |
| 16:15 - 16:45 |
Break |
| 16:45 - 17:10 |
Finding Shortest Non-Separating and Non-Contractible Cycles for Topologically Embedded Graphs
S. Cabello and B. Mohar |
Min Sum Clustering with Penalties
R. Hassin and E.Or |
A Lookahead Branch-and-Bound Algorithm for the Maximum Quartet Consistency Problem
G. Wu, J. You and G. Lin |
| 17:10 - 17:35 |
Delineating boundaries for imprecise regions
I. Reinbacher, M. Benkert, M. van Kreveld, J. Mitchell and A. Wolff |
Improved Approximation Algorithms for Metric Max TSP
Z. Chen and T. Nagoya |
Computing the Quartet Distance Between Arbitrary Evolutionary Trees.
C. Christiansen, C. Norgaard, S. Pedersen and M. Randers |
| 17:35 - 18:00 |
EXACUS - Efficient and Exact Algorithms for Curves and Surfaces
E. Berberich et al |
Unbalanced Graph Cuts
A. Hayrapetyan, D. Kempe, M. Pal and Z. Svitkina |
|
| 18:00 - 18:05 |
Short break |
| 18:05 - 19:00 |
ESA Bussiness meeting |
| 09:00 - 09:50 |
Invited talk
Cristopher Moore |
| 09:50 - 10:00 |
Short break |
| 10:00 - 10:25 |
Low degree connectivity in ad-hoc networks
L. Kucera |
Optimal integer alphabetic trees in linear time
T. Hu and L. Larmore and J. Morgenthaler |
Using Semi-Definite Programming to Enhance Supertree Resolvability
S. Moran, S. Rao and S. Snir |
| 10:25 - 10:50 |
5-Regular Multi-Graphs are 3-Colorable with Independent of their Size Positive Probability.
J. Díaz et al |
Predecessor Queries in Constant Time?
M. Karpinski and Y. Nekrich |
From Constrained to Unconstrained Maximum Agreement Subtree in Linear Time
H. Ting and Z. Peng |
| 10:50 - 11:20 |
Break |
| 11:20 - 11:45 |
An algorithm for node-capacitated ring routing
A. Frank, Z. Kiraly and B. Kotnyek |
Space Efficient Algorithms for the Burrows-Wheeler Backtransformation
U. Lauther and T. Lukovszki |
Pattern Identification in Biogeography: Metrics and Algorithms for Comparing Area Cladograms
G. Ganapathy, B. Goodson, R. Jansen, V. Ramachandran and T. Warnow |
| 11:45 - 12:10 |
On degree constrained shortest paths
S. Khuller, K. Lee and . Shayman |
Cache-oblivious comparison-based algorithms on multisets
A. Farzan, P. Ferragina, G. Franceschini and J. Ian Munro |
On the Complexity of Several Haplotyping Problems
R. Cilibrasi, L. van Iersel, S. Kelk and J. Tromp |
| 12:10 - 12:35 |
A New Template for Solving p-Median Problems for Trees in Sub-quadratic Time
R. Benkoczi and B. Bhattacharya |
Oblivious vs. Distribution-based Sorting: An Experimental Evaluation
G. Chaudhry and T. Cormen |
A Hidden Markov Technique for Haplotype Reconstruction
P. Rastas, M. Koivisto, H. Mannila and E. Ukkonen |
| 12:35 - 13:00 |
Roll cutting in the curtain industry, or: A well-solvable allocation problem
A. Alfieri, S. van de Velde, G. Woeginger |
Allocating memory in a lock-free manner
A. Gidenstam, M. Papatriantafilou and P. Tsiga |
Algorithms for Imperfect Phylogeny Haplotyping (IPPH) with a Single Homoplasy or Recombination Event
Y. Song, Y. Wu and D. Gusfield |
| 13:00 - 15:00 |
Lunch |
| 15:00 - 15:25 |
Generating Realistic Terrains with Higher-Order Delaunay Triangulations
T. de Kok, Marc van Kreveld, and M. Loffler |
New tools and simpler algorithms for branchwidth
C. Paul and J. Telle |
A Faster Algorithm for Detecting Network Motifs
S. Wernicke |
| 15:25 - 15:50 |
I/O-Efficient Construction of Constrained Delaunay Triangulations
P. Agarwal, L. Arge and K. Yi |
Treewidth Lower Bounds with Brambles
H. Bodlaender, A. Grigoriev and A. Koster |
Reaction Motifs in Metabolic Networks
V. Lacroix, C. Gomes Fernandes and M. Sagot |
| 15:50 - 16:15 |
Convex Hull and Voronoi Diagram of Additively Weighted Points
C. Delage and J. Boissonnat |
Minimal interval completions
P. Heggernes, K. Suchan, I. Todinca and Y. Villanger |
Reconstructing Metabolic Networks Using Interval Analysis
V. Moulton and W. Tucker |
| 16:15 - 16:45 |
Break |
| 16:45 - 17:10 |
A 2-Approximation Algorithm for Sorting by Prefix Reversals
J. Fischer and S. Ginzinger |
Efficient Approximation Schemes for Geometric Problems?
D. Marx |
A 1.375-Approximation Algorithm for Sorting by Transpositions
I. Elias and T. Hartman |
| 17:10 - 17:35 |
Approximating the 2-Interval Pattern problem
M. Crochemore, D. Hermelin, G. Landau and S. Vialette |
Geometric clustering to minimize the sum of cluster sizes
V. Bilo, I. Caragiannis, C. Kaklamanis and P. Kanellopoulos |
A New Tight Upper Bound on the Transposition Distance
A. Labarre |
| 17:35 - 18:00 |
A Loopfree Gray Code for Minimal Signed-Binary Representations
G. Manku and J. Sawada |
Approximation Schemes for Minimum 2-Connected Spanning Subgraphs in Weighted Planar Graphs
A. Berger, A. Czumaj, M.Grigni and H. Zhao |
|
| 09:00 - 09:50 |
Invited talk
Marino Zerial |
| 09:50 - 10:00 |
Short break |
| 10:00 - 10:25 |
Packet Routing and Information Gathering in Lines, Rings and Trees
Z. Azar and R. Zachut |
Efficient c-Oriented Range Searching with DOP-Trees
M. de Berg, H. Haverkort and M. Streppel |
Perfect Sorting by Reversals is Not Always Difficult
S. Berard, A. Bergeron, C. Chauve and C. Paul |
| 10:25 - 10:50 |
Jitter Regulation for Multiple Streams
D. Hay and G. Scalosub |
Matching Point Sets with respect to the Earth Mover's Distance
S. Cabello, P. Giannopoulos, C. Knauer and G. Rote |
Minimum Recombination Histories by Branch and Bound
R. Lyngsoe, Y. Song and J. Hein |
| 10:50 - 11:20 |
Break |
| 11:20 - 11:45 |
Small stretch spanners on dynamic graphs
G. Ausiello and Paolo G. Franciosa and Giuseppe F. Italiano |
Preemptive Scheduling of Independent Jobs on Identical Parallel Machines Subject to Migration Delay
A. Fishkin, K. Jansen, S. Sevastianov and R. Sitters |
A Unifying Framework for Seed Sensitivity and Its Application to Subset Seeds
G. Kucherov, L. Noe and M. Roytberg |
| 11:45 - 12:10 |
An Experimental Study of Algorithms for Fully Dynamic Transitive Closure
I. Krommidas and C. Zaroliagis |
Fairness-Free Periodic Scheduling
J. Sgall, H. Shachnai and T. Tamir |
Generalized Planted (l,d)-Motif Problem with Negative Set
H. Leung and F. Chin |
| 12:10 - 12:35 |
Experimental study of geometric t-spanners
M. Farshi and J. Gudmundsson |
Online Bin Packing with Cardinality Constraints
L. Epstein |
Alignment of Tandem Repeats with Excision, Duplication, Substitution and Indels (EDSI)
M. Sammeth, T. Weniger, D. Harmsen and J. Stoye |
| 12:35 - 13:00 |
Highway Hierarchies Hasten Exact Shortest Path Queries
P. Sanders and D. Schultes |
Fast monotone 3-approximation algorithm for scheduling related machines
A. Kovacs |
The Peres-Shields Order Estimator for Fixed and Variable Length Markov Chains with Applications to DNA Sequence Similarity
D. Dalevi and D. Dubhashi |
| 13:00 - 15:00 |
Lunch |
| 15:00 - 15:25 |
Engineering Planar Separator Algorithms
M. Holzer, G. Prasinos, F. Schulz, D. Wagner and C. Zaroliagis |
An Optimal Algorithm for Querying Priced Information: Monotone Boolean Functions and Game Trees
F. Cicalese and E. Laber |
Multiple Structural RNA Alignment with Lagrangian Relaxation
M. Bauer, G. Klau and K. Reinert |
| 15:25 - 15:50 |
Stxxl: Standard Template Library for XXL Data Sets
R. Dementiev, L. Kettner and P. Sanders |
Online View Maintenance under a Response-Time Constraint
K. Munagala, J. Yang and H. Yu |
Faster Algorithms for Optimal Multiple Sequence Alignment based on Pairwise Comparisons
P. Agarwal, Y. Bilu and R. Kolodny |
| 15:50 - 16:15 |
Negative Cycle Detection
dennis chihim wong and Y. C. Tam |
Online Primal-Dual Algorithms for Covering and Packing Problems
N. Buchbinder and J. Naor |
Ortholog Clustering on a Multipartite Graph
A. Vashist, C. Kulikowski and I. Muchnik |
| 16:15 - 16:45 |
Break |
| 16:45 - 17:10 |
Efficient Algorithms for Shared Backup Allocation in Networks with Partial Information
Y. Bejerano, J. Naor and A. Sprintson |
Workload-Optimal Histograms on Streams
S. Muthukrishnan, M. Strauss and X. Zheng |
Linear Time Algorithm for Parsing RNA Secondary Structure
B. Rastegari and A. Condon |
| 17:10 - 17:35 |
Using Fractional Primal-Dual to Schedule Split Intervals with Demands
R. Bar-Yehuda and D. Rawitz |
Finding Frequent Patterns in a String in Sublinear Time
P. Berenbrink, F. Ergun and T. Friedetzky |
A Compressed Format for Collections of Phylogenetic Trees and Improved Consensus Performance
R. Boyer, W. Hunt and S. Nelesen |
| 17:35 - 18:00 |
An approximation algorithm for the minimum latency set cover problem
R. Hassin and A. Levin |
Online Occlusion Culling
G.Frahling and J. Krokowski |
|
|
Conference dinner |
| 09:00 - 09:50 |
Invited talk
Seffi Naor |
| 09:50 - 10:00 |
Short break |
| 10:00 - 10:25 |
Shortest Paths in Matrix Multiplication Time
P. Sankowski |
The Hardness of Network Design for Unsplittable Flow with Selfish Users
Y. Azar and A. Epstein |
Optimal protein threading by cost-splitting
P. Veber, N. Yanev, R. Andonov and V. Poirriez |
| 10:25 - 10:50 |
Computing common intervals of K permutations, with applications to modular decomposition of graphs
A. Bergeron, C. Chauve, F. de Montgolfier, M. Raffinot |
Approximation and Complexity of k-Splittable Flows
R. Koch, I. Spenke and M. Skutella |
Efficient Parameterized Algorithm for Biopolymer Structure-Sequence Alignment
Y. Song, C. Liu, X. Huang, R. Malmberg, Y. Xu and L. Cai |
| 10:50 - 11:20 |
Break |
| 11:20 - 11:45 |
Greedy Routing in Tree-Decomposed Graphs
P. Fraigniaud |
The conference call search problem in wireless networks
L. Epstein and A. Levin |
Rotamer/Rotamer Energy Calculations Using a Trie Data Structure
A. Leaver-Fay, J. Snoeyink and B. Kuhlman |
| 11:45 - 12:10 |
Making Chord Robust to Byzantine Attacks
A. Fiat, J. Saia and M. Young |
SONET ADMs minimization with divisible paths
L. Epstein and A. Levin |
Improved Maintenance of Molecular Surfaces using Dynamic Graph Connectivity
E. Eyal and D. Halperin |
| 12:10 - 12:35 |
Bucket Game with Applications to Set Multicover and Dynamic Page Migration
M. Bienkowski and J. Byrka |
Deterministic Online Optical Call Admission Revisited
S. Krumke and E. Gassner |
The Main Structural Regularities of the Sandwich Proteins
A. Kister, T. Fokas, T. Papatheodorou and I. Gelfand |
| 12:35 - 13:00 |
Bootstrapping a Hop-optimal Network in the Weak Sensor Model
M. Farach-Colton, R. Fernandes and M. Mosteiro |
On Minimizing the Maximum Flow Time in the Online Dial-a-Ride Problem
S. Krumke, W. de Paepe, D. Poensgen, M. Lipmann, A. Marchetti-Spaccamela and L. Stougie |
Discovery of Protein Substructures in EM Maps
K. Lasker, O. Dror, H. Wolfson and R. Nussinov |
| 13:00 - 15:00 |
Lunch |
| 15:00 - 15:25 |
Approximating Integer Quadratic Programs and MAXCUT in Subdense Graphs
A. Björklund |
Approximation Schemes for Packing with Item Fragmentation
H. Shachnai, T. Tamir and O. Yehezkely |
|
| 15:25 - 15:50 |
A Cutting planes Algorithm based upon a Semidefinite relaxation for the Quadratic Assignment Problem
A. Faye and F. Roupin |
Online Removable Square Packing
X. Han, K. Iwama and G. Zhang |
|
| 15:50 - 16:15 |
Approximation complexity of min-max (regret) versions of shortest path, spanning tree, and knapsack
H. Aissi, C. Bazgan and D. Vanderpooten |
The Online Target Date Assignment Problem
S. Heinz, Sven O Krumke, N. Megow, J. Rambau, A. Tuchscherer and T. Vredeveld |
|
| 16:15 - 16:45 |
Break |
| 16:45 - 17:10 |
Complexity of Robust Approximate Zeros
V. Sharma, Z. Du and C. Yap |
Tighter Approximations on Greedy for Maximum Induced Matchings in Regular Graphs
M. Lewenstein and Z. Gotthilf |
|
| 17:10 - 17:35 |
Optimizing a 2D Function Satisfying Unimodality Properties
E. Demaine and S. Langerman |
`Almost stable' matchings in the Roommates problem
D. Abraham, P. Biro and D. Manlove |
|
| 17:35 - 18:00 |
|
A PTAS for the Minimum Dominating Set Problem in Unit Disk Graphs
T. Nieberg and J. Hurink |
|
| 09:10 - 09:35 |
|
Improved Approximation Algorithm for Convex Recoloring of Trees
R. Bar-Yehuda, I. Feldman and D. Rawitz |
Invited talk
Frank Geraets (aka F. Wagner) and Ludger Palz, Deutche Bahn AG
Optimizing the configuration of stations along the German railway network
|
| 09:35 - 10:00 |
|
On the Minimum Load Coloring Problem
N. Ahuja, A. Baltz, B. Doerr, A. Privetivy and A. Srivastav |
| 10:00 - 10:25 |
|
Partial Multicuts in Trees
D. Segev and A. Levin |
Station Location - Complexity and Approximation
S. Mecke, A. Schoebel, and D. Wagner |
| 10:25 - 10:50 |
|
On Approximating Restricted Cycle Covers
B. Manthey |
Line Planning with Minimal Traveling Time
A. Schoebel and S. Scholl |
| 10:50 - 11:20 |
Break |
| 11:20 - 11:45 |
|
Speed Scalingof Tasks with Precedence Constraints
K. Pruhs, R. van Stee and P. Uthaisombut |
Parameter Analysis of Transfers in the Rapid Transit Network Design
R. García, A. Garzon-Astolfi, A. Marín, J.A. Mesa, and F.A. Ortega |
| 11:45 - 12:10 |
|
Scheduling Parallel Jobs with Linear Speedup
A. Grigoriev and M. Uetz |
A Genetic Approach to Train Scheduling on a High-Traffic Railway Line
P. Tormos, A. Lova, L. Ingolotti, F. Barber, M. Abril, and M.A. Salido |
| 12:10 - 12:35 |
|
A note on semi-online machine covering
T. Ebenlendr, J. Noga, J. Sgall and G. Woeginger |
Computer-Based Decision Support for Railway Traffic Scheduling and
Dispatching: a Review of Models and Algorithms. J. Tornquist |
| 12:35 - 13:00 |
|
Exploiting Locality: Approximating Sorting Buffers
R. Bar-Yehuda and J. Laserson |
Engine Assignment Problem Under Some Operation Policy for Railway
Transportation. T. Illes, M. Makai, and Z. Vaik |
| 13:00 - 15:00 |
Lunch |
| 15:00 - 15:25 |
|
On the Hardness and Approximate Fair Cost Allocation in Metric TSP Games
M. Blaeser and S. Lakshminarayanan |
Paying Less for Train Connections with MOTIS
M. Mueller-Hannemann and M. Schnee |
| 15:25 - 15:50 |
|
Symmetry in Network Congestion Games: Pure Equilibria and Anarchy Cost
D. Fotakis, S. Kontogiannis and P. Spirakis |
Applying Analytical and Empirical Methods to the Assessment of Railway Capacity
M. Abril, F. Barber, L. Ingolotti, M.A. Salido, P. Tormos, and A. Lova |
| 15:50 - 16:15 |
|
Improvements for Truthful Mechanisms with Verifiable One-Parameter Selfish Agents
A. Ferrante, G. Parlato, F. Sorrentino and C. Ventre |
|
| 16:15 - 16:45 |
Break |
| 16:45 - 17:10 |
|
Rounding of Sequences and Matrices, with Applications
B. Doerr, T. Friedrich, C. Klein and R. Osbild |
|
| 17:10 - 17:35 |
|
A Better-than-Greedy Algorithm for k-Set Multicover
T. Fujito and H. Kurahashi |
|
| 17:35 - 18:00 |
|
Improved Approximation Algorithms for MAX NAE-SAT and MAX SAT
A. Avidor, I. Berokovitch and U. Zwick |
|
|
|