Accepted papers

in order of submission

  • On the Analysis of Evolutionary Algorithms - A Proof That Crossover Really Can Help
    Thomas Jansen and Ingo Wegener

  • Faster Exact Solutions for Some NP-Hard Problems
    Limor Drori and David Peleg

  • Convex Quadratic Programming Relaxations for Network Scheduling Problems
    Martin Skutella

  • The impact of knowledge on broadcasting time in radio networks
    K. Diks, E. Kranakis, D. Krizanc and A. Pelc

  • Efficient Approximation Algorithms for the Achromatic Number
    Piotr Krysta and Krzysztof Lorys

  • Augmenting an (l-1)-Vertex-Connected Multigraph to a k-Edge-Connected and l-Vertex-Connected Multigraph
    Toshimasa Ishii, Hiroshi Nagamochi and Toshihide Ibaraki

  • Motif statistics
    Pierre Nicodeme, Bruno Salvy and Philippe Flajolet

  • Off-line Temporary Tasks Assignment
    Y. Azar and O. Regev

  • Random Cayley graphs with O(log G) generators are expanders
    Igor Pak

  • On the Informational Asymmetry between Upper and Lower Bounds for Ultrametric Evolutionary Trees
    Ting Chen and Ming-Yang Kao

  • Multipacket routing on 2-D meshes and its applications to fault-tolerant routing
    K. Iwama and E. Miyano

  • Sum Multi-Coloring of Graphs
    Amotz Bar-Noy, Magnus M. Halldorsson, Guy Kortsarz, Ravit Salman and Hadas Shachnai

  • Improving Mergesort for Linked Lists
    Salvador Roura

  • Load Balancing Using Bisectors - A Tight Average-Case Analysis
    Stefan Bischof, Thomas Schickinger and Angelika Steger

  • On computing the diameter of a point set in high dimensional Eucledian space
    Daniele V. Finocchiaro and Marco Pellegrini

  • On constructing suffix arrays in external memory
    Andreas Crauser and Paolo Ferragina

  • Efficient Algorithms for Integer Programs with Two Variables per Constraint
    Reuven Bar-Yehuda and Dror Rawitz

  • Approximation Schemes for Scheduling on Uniformly Related and Identical Parallel Machines
    Leah Epstein and Jiri Sgall

  • Optimal binary search with two unreliable tests and minimum adptiveness
    Ferdinando Cicalese and Daniele Mundici

  • Geometric Searching over the Rationals
    Bernard Chazelle

  • Dilworth's Theorem and its application for path systems of a cycle - implementation and analysis
    Andras Benczur, Zoltan Kiraly and Joerg Forster

  • Efficient algorithms for on-line symbol ranking compression
    G. Manzini

  • On List Update and Work Function Algorithms
    Eric Anderson, Kris Hildrum, Anna R. Karlin, April Rasala and Michael Saks

  • Threshold phenomena in random lattices and efficient reduction algorithms
    Ali Akhavi

  • Approximation Algorithms for the Traveling Purchaser Problem and its Variants in Network Design
    R. Ravi and F.S. Salman

  • A nearly linear-time approximation scheme for the Euclidean k-median problem
    Stavros G. Kolliopoulos and Satish Rao

  • On 2-coverings and 2-packings of laminar families
    J.Cheriyan, T.Jordan and R.Ravi

  • Quartet cleaning: Improved algorithms and simulations
    Vincent Berry, Tao Jiang, Paul Kearney, Ming Li and Todd Wareham

  • IP Address Lookup Made Fast and Simple
    Crescenzi, Dardini and Grossi

  • A Decomposition Theorem for Maximum Weight Bipartite Matchings with Applications in Evolutionary Trees
    M.Y. Kao, T.W. Lam, W.K. Sung and H.F. Ting

  • Efficient Searchingfor Multi-Dimensional Data Made Simple
    E. Nardelli, M. Talamo and P. Vocca

  • On Finding the Maximum Number of Disjoint Cuts in Seymour Graphs
    Alexander A. Ageev

  • Approximate Protein Folding in the HP Side Chain Model on Extended Cubic Lattices
    Volker Heun

  • Provably good and practical strategies for non-uniform data management in networks
    F. Meyer auf der Heide, B. Voecking and M. Westermann

  • On-line load Balancing in a Hierarchical Server Topology
    Amotz Bar-Noy, Ari Freund and Seffi Naor

  • Strategies for Searching with Different Access Costs
    Eduardo Sany Laber, Ruy Milidiu and Artur Alves Pessoa

  • A polyhedral algorithm for packings and designs
    Lucia Moura

  • Fast and Robust Smallest Enclosing Balls
    Bernd Gaertner

  • Resource Constrained Project Scheduling: Computing Lower Bounds by Solving Minimum Cut Problems
    Rolf H. Moehring, Andreas S. Schulz, Frederik Stork and Marc Uetz

  • The 3-Server Problem in the Plane
    W. Bein, M. Chrobak and L. Larmore

  • Approximation algorithms for restoration capacity planning
    Steven Phillips and Jeff Westbrook

  • A Fully Dynamic Algorithm for Recognizing and Representing Proper Interval Graphs
    Pavol Hell, Ron Shamir and Roded Sharan

  • A Fast General Methodology for Information-Theoretically Optimal Encodings of Graphs
    Xin He, Ming-Yang Kao and Hsueh-I Lu

  • An Optimisation Algorithm for Maximum Independent Set with Applications in Map Labelling
    Karen Aardal and Bram Verweij