Tuesday, July 7

18.00-20.00 Welcome Reception

Welcome reception and registration at the conference venue.

Wednesday, July 8

9.00 Invited Lecture

"Recent Developments in Maximum Flow Algorithms"

A. V. Goldberg, NEC Research Institute, New Jersey

10.00 Break

Session 1

Chair: Viggo Kann

10.30 "An Epsilon-Approximation Algorithm for Weighted Shortest Paths on Polyhedral Surfaces"

L. Aleksandrov, Bulgarian Academy of Sciences, Sofia

M. Lanthier, Carleton University, Ottawa

A. Maheshwari, Carleton University, Ottawa

J. R. Sack, Carleton University, Ottawa

10.55 "Facility Location with Dynamic Distance Functions"

R. Bhatia, University of Maryland

S. Guha, Stanford University

S. Khuller, University of Maryland

Y. J. Sussmann, University of Maryland

11.20 "An Approximation Scheme for Bin Packing with Conflicts"

K. Jansen, IDSIA, Lugano

11.45 "Approximations for the General Block Distribution of a Matrix"

B. Aspvall, University of Bergen

M. M. Halldórsson, University of Iceland, Reykjavik

F. Manne, University of Bergen

12.10 Lunch

Session 2

Chair: Jens Lagergren

14.00 "An optimal algorithm for computing visible nearest foreign neighbors among colored line segments"

T. Graf, Research Center Jülich

K. Veezhinathan, Institute of Mathematical Sciences, Chennai

14.25 "Moving an Angle Around a Region"

F. Hoffmann, Freie Universität Berlin

C. Icking, FernUniversität Hagen

R. Klein, FernUniversität Hagen

K. Kriegel, Freie Universität Berlin

14.50 "Models and Motion Planning"

>M. de Berg, Utrecht University

M. J. Katz, Ben-Gurion University of the Negev

M. Overmars, Utrecht University

A. F. van der Stappen, Utrecht University

>J. Vleugels, Utrecht University

15.15 "Constrained Square-Center Problems"

M. J. Katz, Ben-Gurion University of the Negev

K. Kedem, Ben-Gurion University of the Negev and Cornell University

M. Segal, Ben-Gurion University of the Negev

15.40 Break

Session 3

Chair: Peter Bro Miltersen

16.10 "Worst-Case Efficient External-Memory Priority Queues"

G. S. Brodal, Max-Planck-Institut für Informatik, Saarbrücken

J. Katajainen, University of Copenhagen

16.35 "Simple Confluently Persistent Catenable Lists"

H. Kaplan, AT&T labs, New Jersey

C. Okasaki, Carnegie Mellon University

R. E. Tarjan, Princeton University

17.00 "Improved Upper Bounds for Time-Space Tradeoffs for Selection with Limited Storage"

V. Raman, The Institute of Mathematical Sciences, Chennai

S. Ramnath, St Cloud State University

17.25 "Probabilistic data structures for Priority Queues"

R. Sridhar, IIT, Madras

K. Rajasekar, IIT, Madras

C. Pandu Rangan, IIT, Madras

18.10 Business Meeting

Thursday, July 9

9.00 Invited Lecture

"Extractors for Weak Random Sources and their Applications"

D. Zuckerman, University of Texas at Austin

Session 4

Chair: David Peleg

10.30 "Comparator Networks for Binary Heap Construction"

G. S. Brodal, Max-Planck-Institut für Informatik, Saarbrücken

M. C. Pinotti, Istituto di Elaborazione della Informazione, Pisa

10.55 "Two-Variable Linear Programming in Parallel"

D. Z. Chen, University of Notre Dame

J. Xu, University of Notre Dame

11.20 "Optimal Deterministic Protocols for Mobile Robots on a Grid"

R. Grossi, Università di Firenze

A. Pietracaprina, Università di Padova

G. Pucci, Università di Padova

11. 45 "Concurrent Multicast in Weighted Networks"

G. De Marco, Università di Salerno

L. Gargano, Università di Salerno

U. Vaccaro, Università di Salerno

12.10 Lunch

13.30 Excursion

Boat excursion and visit to the Wasa museum .

19.00 Conference Dinner

Conference dinner at restaurant Gondolen.

Friday, July 10

9.00 Invited Lecture

"Some Recent Strong Inapproximability Results"

J. Håstad, KTH, Stockholm

10.00 Break

Session 5

Chair: Valerie King

10.30 "Minimal Elimination of Planar Graphs"

E. Dahlhaus, University of Cologne and University of Bonn

10.55 "Memory requirements for table computations in partial k -tree algorithms"

B. Aspvall, University of Bergen

A. Proskurowski, University of Oregon

J. A. Telle, University of Bergen

11.20 "Formal Language Constrained Path Problems"

C. Barrett, Los Alamos National Laboratory

R. Jacob, Los Alamos National Laboratory

M. Marathe, Los Alamos National Laboratory

11.45 "Local Search Algorithms for SAT: Worst-Case Analysis"

E. A. Hirsch, Steklov Institute of Mathematics at St.Petersburg

12.10 Lunch

Session 6

Chair: Bengt Aspvall

14.00 " Speed is More Powerful than Clairvoyance"

P. Berman, The Pennsylvania State University

C. Coulston, The Pennsylvania State University

14.25 "Randomized Online Multi-threaded Paging"

S. S. Seiden, Technische Universität Graz

14.50 "Determinant: Old Algorithms, New Insights"

M. Mahajan, Institute of Mathematical Sciences, Chennai

V Vinay, Indian Institute of Science, Bangalore

15.15 "Solving Fundamental Problems on Sparse-Meshes"

J. F. Sibeyn, Max-Planck-Institut für Informatik, Saarbrücken

15.40 Break

Session 7

Chair: Stefan Arnborg

16.10 "Output-Sensitive Cell Enumeration in Hyperplane Arrangements"

N. Sleumer, ETH, Zürich

16.35 "Fast and efficient computation of additively weighted Voronoi cells

for applications in molecular biology"

H. M. Will, ETH, Zürich

17.00 "On the Number of Regular Vertices of the Union of Jordan Regions"

B. Aronov, Polytechnic University, Brooklyn

A. Efrat, Tel Aviv University

D. Halperin, Tel Aviv University

M. Sharir, Tel Aviv University and Courant Institute of Mathematical Sciences, New York

17.25 "Distribution-sensitive algorithms"

S. Sen, IIT, New Delhi

N. Gupta, IIT, New Delhi

17.50 End of SWAT`98