Algorithms and Experiments (ALEX98)
Building bridges between theory and applications
Trento, Italy, February 9 - 11, 1998

Conference Program

Invited talks last 40 minutes, regular talks 20 minutes.

Registration (9:00 - 9:50)

Welcome address (9:50 - 10:00)

Session I Chairman: Prabhakar Raghavan (10:00 - 11:40)

Invited talk: Peter Widmayer (ETH Zurich, Switzerland)
"Distributed data structures - concepts and design choices"

* An Approximation Algorithm for the Maximum Cut Problem and its Experimental Analysis , A. Bertoni, P. Campadelli and G. Grossi

* A Seed-Growth Heuristic for Graph Bisection , Joe Marks, Wheeler Ruml, Stuart M. Shieber and J. Thomas Ngo

* Transitive Closure Algorithm MEMTC and its Performance Analysis , Vesa Hirvisalo, Esko Nuutila, Eljas Soisalon-Soininen

Coffe break (11:40 - 12:00)

Session II Chairman: Panos Pardalos (12:00 - 12:40)

Invited talk: Rainer E. Burkard (Technische Universitaet Graz, Austria)
"Fast algorithms for obnoxious location problems"

Lunch pause ----------------------------------

Session III Chairman: Peter Widmayer (14:20 - 16:00)

Invited talk: Panos Pardalos (University of Florida, USA)
"Heuristics for Large Max Clique Problems Based on Continuous Approaches"

* A Dynamic Programming Approach for Timing and Designing Clique Algorithms, Wendy Myrvold, Tania Prsa, Neil Walker

* Designing Algorithms by Sampling, Mark K. Goldberg, David L. Hollinger

* On Very Large Maximum Clique Problems, J. Abello, P. M. Pardalos and M. G. C. Resende

Coffe break (16:00 - 16:20)

Session IV Chairman: Catherine McGeoch (16:20 - 18:00)

Invited talk: Prabhakar Raghavan (IBM Almaden, USA)
"Mining information networks: the CLEVER project at IBM Almaden"

(software and tools session)

* A Software Library of Dynamic Graph Algorithms , David Alberts, Giuseppe Cattaneo, Giuseppe F. Italiano, Umberto Nanni, Christos D. Zaroliagis

* JAZ: Java Algorithm visualiZer. A Multi-Platform Collaborative Tool for Teaching and Testing Graph Algorithms , Giancarlo Bongiovanni, Pierluigi Crescenzi, Gabriella Rago

* Make It! --- Generating and Maintaining Makefiles Automatically , Sven Schönherr and Alexander Wolff

Session V Chairman: Rainer Burkard (8:20 - 9:00)

Invited talk: Catherine McGeoch (Amherst College, USA)
"Open Problems in Experimental Analysis of Algorithms"

Panel Discussions, Open Problems Session Chairman: Catherine McGeoch (9:00 - 10:30)

Catherine McGeoch and other speakers will introduce discussion themes . An informal discussion between panelists and participants will follow.

Coffe break, arrangements (10:30 - 11:00)

Social Activities

Arrangements will be made at the workshop secretariat (Mr. Micheletti).
In particular, a bus will pick up participants from the central hotels for the skiing trip.
A visit of the town and of Buonconsiglio castle will be organized for the others in the afternoon.

Social Dinner Ristorante Chiesa, Parco San Marco (20:00)
*** The social dinner is kindly offered by the municipality of Trento ***

Session VI Chairman: Maurizio Bonuccelli (9:00 - 10:40)

Invited talk: Afonso Ferreira (CNRS, LIP-ENS, Lyon, France)
"Discrete algorithms: practical and efficient, although parallel"

* Experimenting an Approximation Algorithm for the LCS , P. Bonizzoni, M. D'Alessandro, G. Della Vedova and G. Mauri

* Fast Address Look-Up for Internet Routers , Stefan Nilsson and Gunnar Karlsson

* Approximation Heuristics and Benchmarkings for the MinLA Problem , Jordi Petit i Silvestre

Coffe break (10:40 - 11:00)

Session VII Chair: Dorit Hochbaum (11:00 - 12:40)

Invited talk: Silvano Martello (University of Bologna, Italy)
"Two- and Three-Dimensional Bin Packing Problems"

* Unbounded Knapsack Problem: New Results , Vincent Poirriez and Rumen Andonov

* The One-Dimensional Cutting Stock Problem: a Linear Programming Algorithm Based on Hyperflows , Maddalena Nonato, Maria Grazia Scutellà

* Efficient Algorithms and Codes for k-Cardinality Assignment Problems , Mauro Dell'Amico, Andrea Lodi, Silvano Martello

Lunch pause ----------------------------------

Session VIII Chairman: Afonso Ferreira (14:20 - 16:00)

Invited talk: Maurizio Bonuccelli (University of Pisa, Italy)
"Packet Scheduling in Single-Hop Communication Systems"

* Experimental Performance of Shared RSA Modulus Generation , Sara Spalding and Rebecca N. Wright

* Concatenation-Based Greedy Heuristics for the Euclidean Steiner Tree Problem , Martin Zachariasen, Pawel Winter

* The Disk-Covering Method for Tree Reconstruction , Daniel Huson, Scott Nettles, Laxmi Parida, Tandy Warnow and Shibu Yooseph

Coffe break (16:00 - 16:20)

Session IX Chairman: Silvano Martello (16:20 - 18:00)

Invited talk: Dorit Hochbaum (Berkeley, USA)
"A new algorithm and a new simplex algorithm for the maximum flow problem based on an old algorithm for the open pit mining problem."

* Covering Trains by Stations or The Power of Data Reduction , Karsten Weihe

* Bandwidth and Profile Reduction of Sparse Matrices: an Experimental Comparison of New Heuristics , Alessandra Esposito, Federico Malucelli, Luciano Tarricone

* Compression of Sparse Matrices: Achieving Almost Minimal Table Sizes , Nicola Galli, Bernhard Seybold and Klaus Simon

Party and Wine Tasting Session (18:30)
Open only to people travelling by train or plane (not by car, ... unless one leaves the next day)