Algorithms - ESA'99

ESA'99 Program.- Adaptively-Secure Distributed Public-Key Systems.- How Long Does a Bit Live in a Computer?.- Approximation Algorithms for the Traveling Purchaser Problem and Its Variants in Network Design.- The Impact of Knowledge on Broadcasting Time in Radio Networks.- Multipacket Routing on 2-D Meshes and Its Application to Fault-Tolerant Routing.- IP Address LookupMade Fast and Simple.- On-Line Load Balancing in a Hierarchical Server Topology.- Provably Good and Practical Strategies for Non-uniform Data Management in Networks.- Approximation Algorithms for Restoration Capacity Planning.- Efficient Algorithms for Integer Programs with Two Variables per Constraint.- Convex Quadratic Programming Relaxations for Network Scheduling Problems.- Resource-Constrained Project Scheduling:Computing Lower Bounds by Solving Minimum Cut Problems.- Approximation Schemes for Scheduling on Uniformly Related and Identical Parallel Machines.- Off-Line Temporary Tasks Assignment.- Load Balancing Using Bisectors - A Tight Average-Case Analysis.- On the Analysis of Evolutionary Algorithms - A Proof That Crossover Really Can Help.- Motif Statistics.- Approximate Protein Folding in the HP Side Chain Model on Extended Cubic Lattices (Extended Abstract).- On Constructing Suffix Arrays in External Memory.- Strategies for Searching with Different Access Costs.- On the Informational Asymmetry between Upper and Lower Bounds for Ultrametric Evolutionary Trees.- Optimal Binary Search with Two Unreliable Tests and Minimum Adaptiveness.- Improving Mergesort for Linked Lists.- Efficient Algorithms for On-Line Symbol Ranking Compression.- On List Update and Work Function Algorithms.- The 3-Server Problem in the Plane.- Quartet Cleaning: Improved Algorithms and Simulations.- Fast and RobustSmallest Enclosing Balls.- Efficient Searching for Multi-dimensional Data Made Simple.- Geometric Searching over the Rationals.- On Computing the Diameter of a Point Set in High Dimensional Euclidean Space.- A Nearly Linear-Time Approximation Scheme for the Euclidean k-median Problem.- Sum Multi-coloring of Graphs.- Efficient Approximation Algorithms for the Achromatic Number.- Augmenting a(k-1)-Vertex-ConnectedMultigraph to an ?-Edge-Connected and k-Vertex-Connected Multigraph.- An Optimisation Algorithm for Maximum Independent Set with Applications in Map Labelling.- A Decomposition Theorem for MaximumWeight Bipartite Matchings with Applications to Evolutionary Trees.- Faster Exact Solutions for Some NP-Hard Problems.- A Polyhedral Algorithm for Packings and Designs.- Threshold Phenomena in Random Lattices and Efficient Reduction Algorithms.- On Finding the Maximum Number of Disjoint Cuts in Seymour Graphs.- Dilworth's Theorem and Its Application for Path Systems of a Cycle-Implementation and Analysis.- On 2-Coverings and 2-Packings of Laminar Families.- Random Cayley Graphs with O(log|G|) Generators Are Expanders.- A Fully Dynamic Algorithm for Recognizing and Representing Proper Interval Graphs.- A Fast General Methodology for Information-Theoretically Optimal Encodings of Graphs.