Algorithms - ESA'99

1. Front Matter

   Pages I-XII

   PDF

2. ESA’99 Program

   Pages 1-3

3. Adaptively-Secure Distributed Public-Key Systems

   • Yair Frankel, Philip MacKenzie, Moti Yung

   Pages 4-27

4. How Long Does a Bit Live in a Computer?

   • Bernhard Korte

   Pages 28-28

5. Approximation Algorithms for the Traveling Purchaser Problem and Its Variants in Network Design

   • R. Ravi, F. S. Salman

   Pages 29-40

6. The Impact of Knowledge on Broadcasting Time in Radio Networks

   • Krzysztof Diks, Evangelos Kranakis, Danny Krizanc, Andrzej Pelc

   Pages 41-52

7. Multipacket Routing on 2-D Meshes and Its Application to Fault-Tolerant Routing

   • Kazuo Iwama, Eiji Miyano

   Pages 53-64

8. IP Address LookupMade Fast and Simple

   • Pierluigi Crescenzi, Leandro Dardini, Roberto Grossi

   Pages 65-76

9. On-Line Load Balancing in a Hierarchical Server Topology

   • Amotz Bar-Noy, Ari Freund, Joseph (Seffi) Naor

   Pages 77-88

10. Provably Good and Practical Strategies for Non-uniform Data Management in Networks

    • Friedhelm Meyer auf der Heide, Berthold Vöcking, Matthias Westermann

    Pages 89-100

11. Approximation Algorithms for Restoration Capacity Planning

    • Steven J. Phillips, Jeffery R. Westbrook

    Pages 101-115

12. Efficient Algorithms for Integer Programs with Two Variables per Constraint

    • Reuven Bar-Yehuda, Dror Rawitz

    Pages 116-126

13. Convex Quadratic Programming Relaxations for Network Scheduling Problems

    • Martin Skutella

    Pages 127-138

14. Resource-Constrained Project Scheduling:Computing Lower Bounds by Solving Minimum Cut Problems

    • Rolf H. Möhring, Andreas S. Schulz, Frederik Stork, Marc Uetz

    Pages 139-150

15. Approximation Schemes for Scheduling on Uniformly Related and Identical Parallel Machines

    • Leah Epstein, Jiří Sgall

    Pages 151-162

16. Off-Line Temporary Tasks Assignment

    • Yossi Azar, Oded Regev

    Pages 163-171

17. Load Balancing Using Bisectors — A Tight Average-Case Analysis

    • Stefan Bischof, Thomas Schickinger, Angelika Steger

    Pages 172-183

18. On the Analysis of Evolutionary Algorithms — A Proof That Crossover Really Can Help

    • Thomas Jansen, Ingo Wegener

    Pages 184-193

19. Motif Statistics

    • Pierre Nicodème, Bruno Salvy, Philippe Flajolet

    Pages 194-211

20. Approximate Protein Folding in the HP Side Chain Model on Extended Cubic Lattices (Extended Abstract)

    • Volker Heun

    Pages 212-223

The 7th Annual European Symposium on Algorithms (ESA ’99) is held in Prague, Czech Republic, July 16-18, 1999. This continued the tradition of the meetings which were held in – 1993 Bad Honnef (Germany) – 1994 Utrecht (Netherlands) – 1995 Corfu (Greece) – 1996 Barcelona (Spain) – 1997 Graz (Austria) – 1998 Venice (Italy) (The proceedingsof previousESA meetings were publishedas Springer LNCS v- umes 726, 855, 979, 1136, 1284, 1461.) In the short time of its history ESA (like its sister meeting SODA) has become a popular and respected meeting. The call for papers stated that the “Symposium covers research in the use, design, and analysis of ef?cient algorithms and data structures as it is carried out in c- puter science, discrete applied mathematics and mathematical programming. Papers are solicited describing original results in all areas of algorithmic research, including but not limited to: Approximation Algorithms; Combinatorial Optimization; Compu- tional Biology; Computational Geometry; Databases and Information Retrieval; Graph and Network Algorithms; Machine Learning; Number Theory and Computer Algebra; On-line Algorithms; Pattern Matching and Data Compression; Symbolic Computation.

• Approximization
• Computational Mathematics
• Discrete Mathematics
• Efficient Algorithms
• algorithms
• combinatorial optimization
• data compression
• database
• databases
• optimization
• algorithm analysis and problem complexity
• data structures

• Department of Applied Mathematics and DIMATIA Centre, Charles University, Prague 1, Czech Republic

  Jaroslav Nešetřil

Policies and ethics