FUN '01

Fun with Algorithms

THE ISLAND OF ELBA, ITALY
May 29 - 31, 2001

``$\ldots$ pleasure has probably been the main goal all along. But I hesitate to admit it, because computer scientists want to mantain their image as hard-working individuals who deserve high salaries. Sooner or later society will realise that certain kinds of hard work are in fact admirable even though they are more fun than just about anything else.''

(KNUTH D.E., The Stanford Graph Base. A Platform for Combinatorial Computing)

General Information

FUN '01 concerns, to a general extent, the use, design and analysis of algorithms and data structures. In particular of interest are results that provide amusing, witty but nonetheless original and scientifically profound contributions to the areas of approximation algorithms, biological algorithms, combinatorial algorithms, distributed algorithms, evolutionary algorithms, geometrical algorithms, mobile algorithms, network algorithms, optimization algorithms, parallel algorithms, randomized algorithms, and web algorithms.

The workshop will take place in a resort of the Island of Elba (Isola d'Elba), famous for its white sand, deep blue sea and fascinating nature. Ancient Romans were the first to choose the island as one of their favourite places to spend their holidays. The island became the small kingdom of Napoleon as witnessed by some local, historical places. At the end of May, typical temperatures are in the mid-20's C (upper-70's F), cooling down in the evening.

Transportation

The most convenient airport to reach the Island of Elba is Rome, serviced by the major world airlines. Roma Termini, the main train station, can be easily reached from Fiumicino Airport by a shuttle train (Lit. 17.000). It then takes about 4-5 hours to reach the Island of Elba. From Roma Termini, Campiglia Marittima can be reached by train in about 2:30 hours. At this point, Piombino Scalo can be reached in about 30 minutes by commuting in Campiglia Marittima, where a ferry boat is available to go to Portoferraio (Isola d'Elba) in about 1 hour. Alternatively, an air-craft takes 30 minutes. More information is available at the Internet sites www.fs-on-line.com for trains and www.elbacom.it/home.en.html for ferries. As far as ferries are concerned, early registration is strongly recommended for those willing to bring a car.

SHUTTLE SERVICE: please ask travel agency Tesi Viaggi at your arrival in Elba (address: Calata Italia 8, Portoferraio; tel. +39-0565-930222, fax +39-0565-915368.)

Currency Exchange

Approximate Exchange Rate: USD 1 is approximately Lit. 2,100-2,200. Exchange bureaus can be found at local banks; banks are closed from 1:30 p.m. to 2:30 p.m. and after 3:30 p.m. on weekdays and throughout weekends.

Accommodations

Blocks of rooms have been reserved at the hotels listed below. They are all located in Procchio, Isola d'Elba. The prices listed below are intended to be per person.
Hotel Del Golfo$^{****}$

Lit. 225,000 (in single room), Lit. 175,000 (in double room), breakfast and dinner included. This is the workshop site.
Hotel Villa Verde$^{***}$

Lit. 150,000 (in single room), Lit. 90,000 (in double room), breakfast and dinner included. At walking distance from the workshop site.
Hotel Monnalisa$^{***}$

Lit. 85,000 (in single room), Lit. 75,000 (in double room), breakfast and dinner included. At walking distance from the workshop site.
A small number of low cost accomodations (no meals) can be provided in small apartments near the beach and at walking distance from the conference site, priced Lit. 40.000/day per person in 1 room apt. for 2 persons or in 2 rooms apt. for 3 persons.
All rates include taxes. Advance payment is not required and major credit cards are accepted. All the reservations (hotels or apartments) must be made through the local travel agent:

Antonella Giuzio
Agenzia Viaggi e Turismo Tesi
E-mail: anto.tesi@elbalink.it
Tel: +39-0565-930222
Fax: +39-0565-915368

Location of Events

Workshop and lodging facilities are all within 5 minutes walk in the Island of Elba. The workshop site is Hotel del Golfo in Procchio, where a swimming pool, tennis courts, and reserved beach are freely available to the partecipants of FUN 01.

FUN '01 REGISTRATION FORM

Name (first, last):

Name tag should read:

Affiliation:

Address:

Phone: Fax:

E-mail:


Check your dietary preference:

Vegetarian No Restriction


Workshop registration includes the proceedings, the social event, the banquet on Wednsday evening, and coffee breaks. Proceedings and workshop banquet are not included in the student registration fees.


The deadline for early registration is May 15, 2001.


Please circle selection:


 Registration: Early Late
 Regular Lit. 290,000 Lit. 340,000
 Student Lit. 120,000 Lit. 170,000


 Additional Tickets: Number Amount
 Banquet (Lit.  50,000 each) ________ __________


 Hotel Single Double
 (choose one)    
 $\Box$ Del Golfo ____ Lit. 225,000 ____ Lit. 175,000
 $\Box$ Villa Verde ____ Lit. 150,000 ____ Lit. 90,000
 $\Box$ Monnalisa ____ Lit. 85,000 ____ Lit. 75,000


Room type (circle one):
$\bullet$ single (1 bed)
$\bullet$ double (2 beds)
$\bullet$ double (1 bed) shared with:


Total amount: Lit.

Please include a completed registration form with your payment. Fees can be paid by bank draft or check or credit card (only VISA accepted). Payment should be made in Italian Lira (ITL).

Please choose the desired way of payment:

  1. Charge VISA credit card:

    Total Amount Charged: Lit.
    Cardholder's Name
    Card Number
    Expiration Date
    Cardholder's Signature

  2. Bank transfer made payable to the bank account:

    Monte dei Paschi di Siena
    Filiale di Portoferraio (Li), Italy
    account no. 9638.02
    CAB 70740.6 ABI 1030

The registration form and a copy of the payment must be mailed to:

Antonella Giuzio
Agenzia Viaggi e Turismo Tesi
Calata Italia 8
I-57037 Portoferraio (Li)
E-mail: anto.tesi@elbalink.it
Tel.: +39-0565-930222
Fax.: +39-0565-915368



FUN '01 PROCEEDINGS

The proceedings for FUN '01 will be published by Carleton Scientific, and will available at the workshop (extra proceedings copies can be purchased at Lit. 90.000 each).

FUN '01 Program
Workshop site: Hotel Del Golfo


TUESDAY, MAY 29, 2001

8:00
Workshop Registration

Invited Talk

9:00
Fun with Games

C. Papadimitriou, Berkley Univ., USA.

10:00
Coffee Break

Session 1

10:30
Fun Sort

T. Biedl, T. Chan, E.D. Demaine, Univ. of Waterloo, Canada; R. Fleischer, M. Golin, Hong Kong Univ., China; J. I. Munro, Univ. of Waterloo, Canada.

11:00
On Searching Strategies, Parallel Questions, and Delayed Answers

F. Cicalese, L. Gargano, U. Vaccaro, Univ. di Salerno, Italy.

11:30
Using Busy Signal to Speed-Up Mutual Search

S. Dobrev, Slovak Academy of Sciences, Slovak Republic.

12:00
End of Session

Invited Talk

15:30
Graph Monsters

F. Luccio, Univ. of Pisa, Italy.

16:30
Coffee Break

Session 2

17:00
The Geometry of Carpentry and Joinery

P. Morin, McGill Univ., Canada; J. Morrison, Carleton Univ., Canada.

17:30
Efficient Optimal Greedy Algorithms for Room Allocation

V. Ciriani, N. Pisanti, A. Bernasconi Univ. di Pisa, Italy.

18:00
Reachability Problem in a T-Shaped Rectilinear Polygon

A. Mohades, M. Razzazi, Amirkabir Univ. of Technology, Iran.

18:30
End of Session

WEDNSDAY, MAY 30, 2001

Invited Talk

9:00
Fun with Algebraic Topology and Distributed Computing

M. Herlihy, Brown Univ., USA.

10:00
Coffee Break

Session 3

10:30
Approximation Algorithms for Minimum-Time Broadcast Under the Edge-Disjoint Paths Mode

P. Fraigniaud, Univ. Paris-Sud, France.

11:00
Need a Fleet? Use the Force!

V. Gervasi, G. Prencipe Univ. di Pisa, Italy.

11:30
Buses for Anonymous Message Delivery

A. Beimel, S. Dolev, Ben-Gurion Univ. of the Negev, Israel.

Last Minute Talks

12:00
On Indexing and Compressing Large Data Collections

P. Ferragina, Univ. di Pisa, Italy; G. Manzini, Univ. del Piemonte Orientale, Italy.

12:30
On The Complexity of Computing Lottery Scheme

P. Crescenzi, F. Montecalvo, G. Rossi, Univ. di Firenze, Italy.

13:00
End of Session

Session 4

14:45
Coffee Break

15:00
The Area of Parallelogram Polyominoes And a Tiling Game

A. Del Lungo, Univ. di Siena, Italy; M. Nivat, univ. Denis Diderot 2, France; R. Pinzani, S. Rinaldi, Univ. di Firenze., Italy.

15:30
Waiting Patterns for a Printer

D. Merlini, R. Sprugnoli, M. C. Verri, Univ. di Firenze, Italy.

16:00
Trees as Sets of Positive Integers

M. Torelli, Univ. di Milano, Italy.

16:30
End of Session

17:00
Social Event

21:00
Social Dinner

THURSDAY, MAY 31, 2001

Invited Talk

9:00
Fibonacci, Thue-Morse and Unavoidable Patterns

A. Restivo, Univ. di Palermo, Italy.

10:00
Coffee Break

Session 5

10:30
Problem Classification Using Program Checking

C. S. Collberg, Univ. of Arizona, USA; T. A. Proebsting, Microsoft Research, USA.

11:00
A New Analysis Technique For The Sprouts Game

R. Focardi, Univ. di Venezia, Italy; F. L. Luccio, Univ. di Trieste.

11:30
TANTRIX$^{TM}$ Rotation Puzzles Are Intractable

M. Holzer, Institut für Informatik, Germany; W. Holzer.

12:00
End of Session / Workshop

FUN '01 Organization

Workshop Chairs

Elena Lodi, Univ. of Siena, Italy
Linda Pagli, Univ. of Pisa, Italy
Nicola Santoro, Carleton Univ., Canada

Program Committee

Jean-Claude Bermond INRIA Sophia Antipolis, France
Pierluigi Crescenzi Univ. di Firenze, Italy
Frank Dehne Carleton U., Canada
Paolo Ferragina Univ. di Pisa, Italy
Michele Flammini Univ. dell'Aquila, Italy
Paola Flocchini Ottawa U., Canada
Roberto Grossi Univ. di Pisa, Italy
Danny Krizanc Wesleyan U., USA
Elena Lodi Univ. di Siena, Italy, Co-chair
Linda Pagli Univ. di Pisa, Italy, Co-chair
David Peleg Weizmann Inst., Israel
Andrea Pietracaprina Univ. di Padova, Italy
Geppino Pucci Univ. di Padova, Italy
Luca Trevisan Columbia U., USA
Serjo Rajsbaum U.N.A.M., Mexico
Antonio Restivo Univ. di Palermo, Italy
Nicola Santoro Carleton U., Canada, Co-chair
Ugo Vaccaro Univ. di Salerno, Italy
Sebastiano Vigna Univ. di Milano, Italy
Tandy Warnow U. Texas Austin, USA

Local Arrangements Committee
Antonella Giuzio - Agenzia Viaggi e Turismo Tesi - Isola d'Elba

Sponsors

Università di Pisa has provided generous support.