9.00 - 10.00 | Moti Yung: Adaptively Secure Distributed Public-Key Systems (invited talk) |
10.00 | cofee break |
10.30 | R. Ravi and F.S. Salman: Approximation Algorithms for the Traveling Purchaser Problem and its Variants in Network Design |
10.55 | K. Diks, E. Kranakis, D. Krizanc and A. Pelc: The impact of knowledge on broadcasting time in radio networks |
11.20 | K. Iwama and E. Miyano: Multipacket routing on 2-D meshes and its applications to fault-tolerant routing |
11.45 | P. Crescenzi, L. Dardini and R. Grossi: IP Address Lookup Made Fast and Simple |
12.05 | lunch |
14.00 | A. Bar-Noy, A. Freund and S. Naor: On-line load Balancing in a Hierarchical Server Topology |
14.25 | F. Meyer auf der Heide, B. Voecking and M. Westermann: Provably good and practical strategies for non-uniform data management in networks |
14.50 | S. Phillips and J. Westbrook: Approximation algorithms for restoration capacity planning |
15.10 | break |
15.30 | R. Bar-Yehuda and D. Rawitz: Efficient Algorithms for Integer Programs with Two Variables per Constraint |
15.55 | M. Skutella: Convex Quadratic Programming Relaxations for Network Scheduling Problems |
16.20 | R. H. Moehring, A. S. Schulz, F. Stork and M. Uetz: Resource Constrained Project Scheduling: Computing Lower Bounds by Solving Minimum Cut Problems |
16.40 | break |
17.00 | L. Epstein and J. Sgall: Approximation Schemes for Scheduling on Uniformly Related and Identical Parallel Machines |
17.25 | Y. Azar and O. Regev: Off-line Temporary Tasks Assignment |
17.50 | S. Bischof, T. Schickinger and A. Steger: Load Balancing Using Bisectors - A Tight Average-Case Analysis |
after dinner ESA business meeting |
8.30 | T. Jansen and I. Wegener: On the Analysis of Evolutionary Algorithms - A Proof That Crossover Really Can Help |
8.55 | P. Nicodeme, B. Salvy and Ph. Flajolet: Motif statistics |
9.20 | V. Heun: Approximate Protein Folding in the HP Side Chain Model on Extended Cubic Lattices |
9.45 | A. Crauser and P. Ferragina: On constructing suffix arrays in external memory |
10.05 | break |
10.30 | E. S. Laber, R. Milidiu and A. A. Pessoa: Strategies for Searching with Different Access Costs |
10.55 | Ting Chen, Ming-Yang Kao: On the Informational Asymmetry between Upper and Lower Bounds for Ultrametric Evolutionary Trees |
11.20 | F. Cicalese and D. Mundici: Optimal binary search with two unreliable tests and minimum adptiveness |
11.45 | S. Roura: Improving Mergesort for Linked Lists |
12.05 | lunch |
14.00 | G. Manzini: Efficient algorithms for on-line symbol ranking compression |
14.25 | E. Anderson, K. Hildrum, A. R. Karlin, A. Rasala and M. Saks: On List Update and Work Function Algorithms |
14.50 | W. Bein, M. Chrobak and L. Larmore: The 3-Server Problem in the Plane |
15.10 | break |
15.30 | V. Berry, Tao Jiang, P. Kearney, Ming Li and T. Wareham: Quartet cleaning: Improved algorithms and simulations |
15.55 | B. Gaertner: Fast and Robust Smallest Enclosing Balls |
16.20 | E. Nardelli, M. Talamo and P. Vocca: Efficient Searchingfor Multi-Dimensional Data Made Simple |
16.40 | break |
17.00 | B. Chazelle: Geometric Searching over the Rationals |
17.25 | D. V. Finocchiaro and M. Pellegrini: On computing the diameter of a point set in high dimensional Eucledian space |
17.50 | S. G. Kolliopoulos and S. Rao: A nearly linear-time approximation scheme for the Euclidean k-median problem |
Concert (St. Nicolai Church at Lesser Town) | |
Conference dinner (Ledebourgh gardens under Prague Castle) |
8.30 - 9.30 | B. Korte: How long does a bit live in a computer? (invited talk) |
break | |
10.00 | A. Bar-Noy, M. M. Halldorsson, G. Kortsarz, R. Salman and H. Shachnai: Sum Multi-Coloring of Graphs |
10.25 | P. Krysta and K. Lorys: Efficient Approximation Algorithms for the Achromatic Number |
10.50 | T. Ishii, H. Nagamochi, T. Ibaraki: Augmenting an (l-1)-Vertex-Connected Multigraph to a k-Edge-Connected and l-Vertex-Connected Multigraph |
11.25 | K. Aardal and B. Verweij: An Optimisation Algorithm for Maximum Independent Set with Applications in Map Labelling |
11.50 | M.Y. Kao, T.W. Lam, W.K. Sung and H.F. Ting: A Decomposition Theorem for Maximum Weight Bipartite Matchings with Applications in Evolutionary Trees |
lunch | |
14.00 | D. Peleg and L. Drori: Faster Exact Solutions for Some NP-Hard Problems |
14.25 | L. Moura: A polyhedral algorithm for packings and designs |
14.50 | A. Akhavi: Threshold phenomena in random lattices and efficient reduction algorithms |
15.10 | break |
15.30 | A. A. Ageev: On Finding the Maximum Number of Disjoint Cuts in Seymour Graphs |
15.55 | A. Benczur, Z. Kiraly and J. Forster: Dilworth's Theorem and its application for path systems of a cycle - implementation and analysis |
16.20 | J.Cheriyan, T.Jordan and R.Ravi: On 2-coverings and 2-packings of laminar families |
16.40 | break |
17.00 | I. Pak: Random Cayley graphs with O(log G) generators are expanders |
17.25 | P. Hell, R. Shamir and R. Sharan: A Fully Dynamic Algorithm for Recognizing and Representing Proper Interval Graphs |
17.50 | Xin He, Ming-Yang Kao and Hsueh-I Lu: A Fast General Methodology for Information-Theoretically Optimal Encodings of Graphs |