ALENEX 99 Program.

Friday, January 15th

7:30 Continental Breakfast available until 9:00

8:15 Greetings and announcements

8:30 -- 9:30 Combinatorial Algorithms (Chair Johnson)

• Efficient implementation of the WARM-UP algorithm for the construction of length-restricted prefix codes. Ruy Luiz Milidiú, Artur Alves Pessoa, and Eduardo Sany Laber, PUC-RJ, Rio de Janeiro.
• Implementing weighted b-matching algorithms: insights from a computational study. Matthias Müller-Hannemann and Alexander Schwartz, Technische Unviersität Berlin.
• Designing practical efficient algorithms for symmetric multiprocessors. David R. Helman and Joseph Jájá, University of Maryland

10:00--11:20 Computational Geometry and Graph Drawing (Chair Tamassia)

• Circular drawings of biconnected graphs. Janet M. Six and Ioannis G. Tollis, University of Texas at Dallas
• Heuristics and experimental design for bigraph crossing number minimization. Matthias Stallmann, Franc Brglez, and Debabrata Gosh, N.C. State University.
• Binary space partitions in Plücker Space. David M. Mount and Fan-Tao Pu, University of Maryland.
• Practical point-in-polygon tests using CSG representations of polygons. Robert J. Walker and Jack Snoeyink, UCB

1:00 -- 2:00 Invited talk by Kurt Mehlhorn: From Algorithm to Program

2:00 -- 2:30 break

2:30 -- 5:20 Papers from the Sixth DIMACS Challenge on Near-Neighbor Searches in High-Dimensional Spaces

• 2:30 -- 3:50 Part I: Euclidean Spaces (Chair Goldwasser)
  • Nearest Neighbor Search in Vector Quantization. Kevin Zatloukal, Mary Holland Johnson and Richard Ladner, University of Washington.
  • Analysis of Approximate Nearest Neighbor Searching with Clustered Point Sets. Songrit Maneewongvatana and David Mount, University of Maryland, College Park.
  • Analysis and Improvement of the SR-tree: an Index Structure for Nearest Neighbor Searches. Norio Katayama and Shin'ichi Satoh, NACSIS Japan.
  • Experimentation with an Approximate Nearest Neighbours Search Algorithm based on the Extended General Spacefilling Curves Heuristic. Juan-Carlos Pé rez and Enrique Vidal, Universidad Plité cnica de Valencia.

• 3:50 -- 4:20 break

• 4:20 -- 5:20 Part II: General Metric Spaces (Chair McGeoch)
  • Nearest Neighbor Searching in Metric Spaces: Some Experimental Results. Kenneth L. Clarkson, Bell Labs and Lucent.
  • Excluded Middle Vantage Point Forests for Nearest Neighbor Search. Peter N. Yianilos, NEC Research.
  • Evaluating Some Fast Nearest Neighbor Search Algorithms in Metric Spaces. Luisa Micó and Jose Oncina, Universidad de Alicante.

Saturday, January 16th

7:30 Continental Breakfast available until 9:00

8:15 Greetings and announcements

8:30 --9:40 Software and Applications (Chair Skienna)

• Accessing the internal organization of data structures in the JDSL library. Michael T. Goodrich, Mark Handy, Benoît Hudson, and Roberto Tamassia, Johns Hopkins University and Brown University.
• Object-oriented design of graph oriented data structures. Maurizio Pizzonia and Guiseppe Di Battista, Universitá di Roma.
• A case study on the cost of geometric computing. Stefan Schirra, Max-Planck-Institut.
• (10 minutes for announcements of software libraries and repositories)

10:00--11:20 Applications (Chair Italiano)

• Design and implementation of Fiduccia-Mattheyses heuristic for VLSI netlist partitioning. Andrew E. Caldwell, Andrew B. Kahng and Igor L. Markov, UCLA.
• Algorithms for restoration planning in a telecommunications network. M. Deng, D. F. Lynch, S. J. Phillips, and J. R. Westbrook, AT&T Labs-Research.
• Computing the nxm shortest paths efficiently. Tetsuo Shibuya, IBM Research Division, Tokyo.
• Image watermarking for copyright protection. Gregory L. Heileman, Carlos E. Pizano, Lawrence W. Irwin, and Chaouki T. Abdallah, University of New Mexico.

1:00 -- 2:00 Invited talk by Jon Bentley: Experiments for Algorithm Engineering

2:00 -- 2:15 break

2:15 -- 3:15 Algorithms for NP-Hard Problems (Chair Battiti)

• A self-organizing bin packing heuristic. Janos Csirik, David S. Johnson, Claire Kenyon, Peter W. Shor, and Richard Weber, University of Szeged, AT&T Labs, Université Paris-Sud, and University of Cambridge.
• Finding the right cutting planes for the TSP. Matthew S. Levine, MIT.
• Obstacle-avoiding Euclidean Steiner trees in the plane: an exact algorithm. Martin Zachariasen and Pawel Winter, University of Copenhagen.

3:45 -- 4:45 Data Structures (Chair Karger)

• Adaptive algorithms for cache-efficient trie search. Anurag Acharya, Huican Zhu, and Kai Shen, University of California, Santa Barbara.
• Fast priority queues for cached memory. Peter Sanders, Max-Planck Institut
• Efficient bulk operations on dynamic R-trees. Lars Arge, Klaus H. Hinrichs, Jan Vahrenhold, and Jeffry S. Vitter, Duke University and Westfälische Whilhelms-Universität.