The Sixth


July 8-10 1998
Stockholm, Sweden

/ Tuesday / Wednesday / Thursday / Friday /

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