The Fifth

SCANDINAVIAN WORKSHOP
on
ALGORITHM THEORY

July 3--5, 1996
Reykjavík, Iceland

Supported by:
Nordic Academy for Advanced Study (NorFA),
City of Reykjavík, and Ministry of Education of Iceland.

Upplýsingar fyrir íslenska þáttakendur

Contents

1. Conference Information
2. Program
3. Organizers

Other related pages

1. This document in Postcript and PDF
2. The call-for-participation brochure in PDF, Postscript, DVI, TeX, and asciiform.
3. Call for papers
4. Reykjavik, University of Iceland, Iceland at your fingertips, Travel Facts.

Conference Information

Location: The workshop will be held at the Oddi building on the university campus. It's a white building, shaped as an irregular, asymmetric polygon, placed low center on the campus map inside your folder. Hotel Gardur is placed to the left, marked as ``Student dormitory'' Hotel Loftleidir is down left, outside the map.

Registration desk: Registration will open at 8 am on Wednesday July 3. The registration desk will be open on Wednesday morning, during lunch hours, and sporadically in between. Feel free to ask us about sightseeing possibilities.

Proceedings: Additional copies may be purchased at the workshop for $40 (2700kr) (note the correction).

Lunch: Conference lunch is at the cafeteria on the first floor of the Taeknigardur building (marked on the campus map as ``Centre for Technical Innovation''). Go up from Oddi, cross Sudurgata street and head to a grey and green three-story building across the parking lot. Please bring your badge!

Reception: The City of Reykjavík, along with the Ministry of Education, hosts a reception at 6:30 pm on Wednesday in City Hall for SWAT participants and their accompanying persons. Head west from campus, across Hringbraut blvd, to the new building that stands into the city pond on the far end.

Banquet: The conference dinner will be held on Thursday at a historic site on the small island Videy just outside Reykjavík. Participant are encouraged to present homebrew entertainment or music afterwards. We depart from Hotel Gardur at 7:30 (notice the change) and Hotel Loftleidir five to ten minutes later.

Excursion: On Friday afternoon, we will head out of the city to see some of the unique nature in Iceland. We visit the original geyser Geysir and its constantly spewing brother; the ``golden falls'' Gullfoss; the fault and fissure separated lava fields at Thingvellir national park; and the geothermal active area of Nesjavellir. We hope to do some light mountain hiking, but the actual schedule will be decided on-line, depending on weather and mood. We bring with us a box meal, along with beer and beverages.

There will be an ``open air problem session'' during the excursion. Please contribute some open problems.

Extra tickets: If you would like an extra ticket for the banquet (for a student or a spouse) or for the excursion (for a spouse), please sign up early on Wednesday. The at-cost prices are $70 (4700kr) and $45 (3000kr), respectively.

Program

Wednesday, July 3, 1996

Invited Lecture

9:00

Derandomization via Small Sample Spaces. Noga Alon (Tel-Aviv).

Session 1: 9:50--10:40 am Chaired by Erik M. Schmidt.

9:50

The Randomized Complexity of Maintaining the Minimum. Gerth S. Brodal (Aarhus), Shiva Chaudhuri (Max-Planck-Institut), Jaikumar Radhakrishnan (Tata Institute).

10:45

Faster Algorithms for the Nonemptiness of Streett Automata and for Communication Protocol Pruning. Monika Rauch Henzinger (Cornell), Jan Arne Telle (Bergen).

Coffee Break 10:40--11:00 am

Session 2: 11:00--12:40 noon Chaired by Bengt Aspvall.

11:00

Service-Constrained Network Design Problems. Madhav V. Marathe (Los Alamos), R. Ravi (Carnegie-Mellon), Ravi Sundaram (MIT).

11:25

Approximate Hypergraph Coloring. Pierre Kelsen, Sanjeev Mahajan, and Hariharan Ramesh (Max-Planck-Institut).

11:50

Facility Dispersion and Remote Subgraphs. Barun Chandra (Rice), Magnús M. Halldórsson (Iceland).

12:15

The Constrained Minimum Spanning Tree Problem. R. Ravi (Carnegie-Mellon), M.X. Goemans (MIT).

Lunch Break 12:40--2:00 pm

Session 3: 2:00--3:40 pm Chaired by Rolf Karlsson

2:00

Randomized Approximation of the Constraint Satisfaction Problem. Hoong Chuin Lau and Osamu Watanabe (Tokyo I.Tech).

2:25

On the Hardness of Global and Local Approximation. Hartmut Klauck (Frankfurt).

2:50

Approximation Algorithms for the Maximum Satisfiability Problem. Takao Asano (Chuo), Takao Ono and Tomio Hirata (Nagoya).

3:15

On the Hardness of Approximating the Minimum Consistent OBDD Problem. Kouichi Hirata, Shinichi Shimozono, and Ayumi Shinohara (Kyushu).

Coffee Break 3:40--4:00 pm

Session 4: 4:00--6:05 pmChaired by Takao Nishizeki.

4:00

Computing the Unrooted Maximum Agreement Subtree in Sub-quadratic Time. T.W. Lam, W.K. Sung, and H.F. Ting (Hong Kong).

4:25

Greedily Finding a Dense Subgraph. Yuichi Asahiro and Kazuo Iwama (Kyushu), Hisao Tamaki and Takeshi Tokuyama (IBM Tokyo).

4:50

Using Sparsification for Parametric Minimum Spanning Tree Problems. David Fernández-Baca and Giora Slutzki (Iowa State), David Eppstein (UC Irvine).

5:15

Vertex Partitioning Problems On Partial k-Trees. Arvind Gupta and Damon Kaller (Simon Fraser), Sanjeev Mahajan (Max-Planck-Institut), Tom Shermer (Simon Fraser).

5:40

Making an Arbitrary Filled Graph Minimal by Removing Fill Edges. Jean R.S. Blair (West Point), Pinar Heggernes and Jan Arne Telle (Bergen).

Reception: 7:00 pm.

Thursday, July 4, 1996

Invited Lecture

9:00

Sorting and Searching Revisited. Arne Andersson (Lund).

Session 5: 9:50--10:40 am Chaired by J.R. Sack.

9:50

Lower Bounds for Dynamic Transitive Closure, Planar Point Location, and Parentheses Matching. Thore Husfeldt, Theis Rauhe, and Søren Skyum (Aarhus).

10:15

Optimal Pointer Algorithms for Finding Nearest Common Ancestors in Dynamic Trees. Stephen Alstrup and Mikkel Thorup (Copenhagen).

Coffee Break 10:40--11:00 am

Session 6: 11:00--12:40 noon Chaired by Hjálmtýr Hafsteinsson

11:00

Neighborhood Graphs and Distributed -Coloring. Pierre Kelsen (Max-Planck-Institut).

11:25

Communication Complexity of Gossiping by Short Messages. Luisa Gargano, Adele A. Rescigno, and Ugo Vaccaro (Salerno).

11:50

Optimal Cost Sensitive Distributed Minimum Spanning Tree Algorithms. Teresa Przytycka (Maryland), Lisa Higham (Calgary).

12:15

A Linear Time Algorithm for the Feasibility of Pebble Motion on Trees. Vincenzo Auletta (Salerno), Angelo Monti (Roma), Mimmo Parente and Pino Persiano (Salerno).

Lunch Break 12:40--2:00 pm

Session 7: 2:00--3:40 pm Chaired by Andrzej Lingas

2:00

Linear-Time Heuristics for Minimum Weight Rectangulation. Christos Levcopoulos and Anna Östlin (Lund).

2:25

Visibility with Multiple Reflections. Boris Aronov (Polytechnic, Brooklyn), Alan R. Davis (St. Johns), Tamal K. Dey, Sudebkumar P. Pal, and D. Chithra Prasad (IIT Kharagpur).

2:50

A Fast Heuristic for Approximating the Minimum Weight Triangulation. Christos Levcopoulos and Drago Krznaric (Lund).

3:15

Neighbours on a Grid. Andrej Brodnik (Ljubljana), Ian Munro (Waterloo).

Coffee Break 3:40--4:00 pm

Session 8: 4:00--6:05 pm Chaired by Susanne Albers

4:00

On Two Dimensional Packing. Yossi Azar and Leah Epstein (Tel-Aviv).

4:25

Optimal Orthogonal Drawings of Triconnected Plane Graphs. Therese C. Biedl (Rutgers).

4:50

Walking Streets Faster. Alejandro López-Ortiz (Waterloo), Sven Schuierer (Freiburg).

5:15

Safe and Efficient Traffic Laws for Mobile Robots. Sonne Preminger (Weizmann), Eli Upfal (IBM Almaden).

Business Meeting: 5:40 pm, Oddi

Conference Banquet: 7:00 pm, Videy

Friday, July 5, 1996

Invited Lecture

9:00

Selection: Recent Progress. Mike Paterson (Warwick).

Session 9: 9:50--10:40 am Chaired by Ricardo Baeza-Yates

9:50

Probabilistic Ancestral Sequences and Multiple Alignments. Gaston H. Gonnet and Steven A. Benner (ETH).

10:15

Efficient Algorithms for Lempel-Ziv Encoding. Leszek Gasieniec (Max-Planck-Institut), Marek Karpinski (Bonn), Wojciech Plandowski and Wojciech Rytter (Warsaw).

Coffee Break 10:40--11:00 am

Session 10: 11:00--12:40 noon Chaired by Svante Carlsson

11:00

The Deterministic Complexity of Parallel Multisearch. Armin Bäumker and Wolfgang Dittrich (Paderborn), Andrea Pietracaprina (Padova).

11:25

Priority Queues on Parallel Machines. Gerth S. Brodal (Aarhus).

11:50

Binary Search Trees: How Low Can You Go? Rolf Fagerberg (Odense).

12:15

Boolean Analysis of Incomplete Examples. Endre Boros (Rutgers), Toshihide Ibaraki and Kazuhisa Makino (Kyoto).

Lunch Break 12:40--2:00 pm

Excursion and Open-Air Problem Session:

Depart: 2:00 pm
Return: Midnight

Conference Organizers

Organizing Committee:
Hjálmtýr Hafsteinsson and
Magnús M. Halldórsson (University of Iceland)

Program Committee:
Susanne Albers (Max-Planck-Institut für Informatik)
Bengt Aspvall (University of Bergen)
Ricardo Baeza-Yates (University of Chile)
Svante Carlsson (Luleå Technical University)
Magnús M. Halldórsson (University of Iceland)
Rolf Karlsson (co-chair, Lund University)
Andrzej Lingas (co-chair, Lund University)
Joe Mitchell (SUNY Stony Brook)
Takao Nishizeki (Tohoku University)
Pekka Orponen (University of Helsinki)
Jörg-Rüdiger Sack (Carleton University)
Erik M. Schmidt (University of Aarhus)
Eli Upfal (IBM Almaden)
Moti Yung (IBM Yorktown Heights)

SWAT Steering Committee:
Bengt Aspvall (University of Bergen)
Svante Carlsson (Luleå Technical University)
Hjálmtýr Hafsteinsson (University of Iceland)
Rolf Karlsson (Lund University)
Andrzej Lingas (Lund University)
Erik M. Schmidt (University of Aarhus)
Esko Ukkonen (University of Helsinki)

For further information about the workshop, check out the WWW page:

http://www.hi.is/swat96/

or contact:

Magnús M. Halldórsson
Lofskeytastod (Old Telegraph Office)
University of Iceland
IS-107 Reykjavík, Iceland
Tel: 354--525-4773 (w), 565-7614 (h)
Fax: 354--552-8801
Email: mmh@rhi.hi.is