Algorithms - ESA'99 Book

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