|
|
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 |
|
|
|