SODA '98 Conference Program

This conference program is the complete list of sessions including individual talks and authors. A Program-at-a-Glance is available in an abbreviated table format that will help you make your travel arrangements and decide what talks to attend. Please refer to Program Updates for a list of changes made to this program since it was posted.

Saturday Evening, January 24

5:30 PM-7:30 PM Registration

6:00 PM-8:30 PM
Welcoming Reception
Redwood Room

Sunday Morning, January 25

7:30 AM-4:00 PM Registration
8:00 AM-8:50 AM Continental Breakfast

9:00 AM-10:35 AM Concurrent Sessions

• Session 1

  9:00 AM-10:35 AM
  Chair: Howard Karloff, Georgia Institute of Technology
  Gold Rush A Room

  9:00-9:20 Analysis of a Local Search Heuristic for Facility Location Problems

  Madhukar R. Korupolu, C. Greg Plaxton and Rajmohan Rajaraman, University of Texas, Austin

  9:25-9:45 Minimizing Service and Operation Costs of Periodic Scheduling

  Amotz Bar-Noy, Tel-Aviv University, Israel; Randeep Bhatia, University of Maryland, College Park; Joseph (Seffi) Naor, Technion-Israel Institute of Technoloy, Israel; and Baruch Schieber, IBM T. J. Watson Research Center

  9:50-10:10 A Polynomial-time Approximation Scheme for Mimimum Routing Cost Spanning Trees

  B. Y. Wu, National Tsing Hua University, Taiwan, Republic of China; Giuseppe Lancia, Universit� di Padova, Italy; Vineet Bafna, SmithKline Beecham Pharmaceuticals; K.M. Chao, Providence University, Taiwan, Republic of China; R. Ravi, Carnegie Mellon University; and C.Y. Tang, National Tsing Hua University, Taiwan, Republic of China

  10:15-10:35 A Polynomial-Time Approximation Scheme for Weighted Planar Graph TSP

  Sanjeev Arora, Princeton University; Michelangelo Grigni, Emory University; David Karger, Massachusetts Institute of Technology; Philip Klein, Brown University; and Andrzej Woloszyn, Emory University

• Session 2

  9:00 AM-10:35 AM
  Chair: Madhu Sudan, IBM T. J. Watson Research Center
  Gold Rush B Room

  9:00-9:20 Computing Univariate GCDs over Number Fields

  Michael Monagan, Simon Fraser University, Canada; and Roger Margot, Eidgen�ssische Technische Hochschule-Zurich, Switzerland

  9:25-9:45 Extended Hilbert Irreducibility and Its Applications

  Ming-Deh Huang and Yiu-Chung Wong, University of Southern California

  9:50-10:10 Reconstructing Randomly Sampled Multivariate Polynomials from Highly Noisy Data

  Hal Wasserman, University of California, Berkeley

  10:15-10:35 Computation of Approximate Polynomial Gcds and an Extension

  Victor Y. Pan, Lehman College, City University of New York, Bronx

10:35 AM-11:00 AM Coffee

11:00 AM-12:35 PM Concurrent Sessions

• Session 3

  11:00 AM-12:35 PM
  Chair: Amos Fiat, Tel-Aviv University, Israel
  Gold Rush A Room
  

  11:00-11:20 LRU is Better Than FIFO

  Marek Chrobak and John Noga, University of California, Riverside

  11:25-11:45 On-Line File Caching

  Neal E. Young, Dartmouth College

  11:50-12:10 Competitive Algorithms for Multilevel Caching and Relaxed List Update

  Marek Chrobak and John Noga, University of California, Riverside

  12:15-12:35 Online Throughput-Competitive Algorithm for Multicast Routing and Admission Control

  Ashish Goel, Stanford University; Monika Henzinger, DEC Systems Research Center; and Serge Plotkin, Stanford University

• Session 4

  Chair: Micha Sharir, Tel-Aviv University, Israel
  Gold Rush B Room
  

  11:00-11:20 Kinetic Binary Space Partitions for Intersecting Segments and Disjoint Triangles

  Pankaj K. Agarwal and Jeff Erickson, Duke University; and Leonidas K. Guibas, Stanford University

  11:25-11:45 I/O-Efficient Algorithms for Contour-line Extraction and Planar Graph Blocking

  Pankaj K. Agarwal, Lars Arge, T. M. Murali, Kasturi R. Varadarajan and Jeffrey S. Vitter, Duke University

  11:50-12:10 Collision Detection in Aspect and Scale Bounded Polyhedra

  Subhash Suri and Philip M. Hubbard, Washington University; and John F. Hughes, Brown University

  12:15-12:35 An Efficient Algorithm for the Three-Dimensional Diameter Problem

  Sergei N. Bespamyatnikh, Ural State University, Russia

Sunday Afternoon, January 25

12:35 PM-2:00 PM Lunch (attendees are on their own)

IP1
Algorithms and Geometric Representations of Graphs

2:00 PM-3:00 PM
Chair: Howard Karloff, Georgia Institute of Technology
Gold Rush A Room

To represent a graph in a geometric way is a very natural and old problem. For example, it was proved by Steinitz early in this century that every 3-connected planar graph can be represented as the graph of vertices and edges of a (3-dimensional) polytope.

Representability of a graph in various geometric fashions turns out to be closely related to a number of basic properties of the graph. Moreover, computing these representations often helps in the design of algorithms for purely graph-theoretic problems.

Examples of such techniques include the representation of a graph by considering the edges as "rubber bands", which relate to higher connectivity, and also to mixing properties of random walks; orthogonal representations of graphs, which relate to independence, chromatic number, connectivity and tree-width; and other representations which relate to planarity and linkless embeddability.

Laszlo Lovasz
Department of Computer Science
Yale University

3:05 PM-4:15 PM Concurrent Sessions

• Session 5

  3:05 PM-4:15 PM
  Chair: David Shmoys, Cornell University
  Gold Rush A Room
  

  3:05-3:25 Faster Algorithms for the Quickest Transshipment Problem

  Lisa Fleischer, Cornell University

  3:30-3:50 Exact Arithmetic at Low Cost - A Case Study in Linear Programming

  Bernd G�rtner, Eidgen�ssische Technische Hochschule-Zurich, Switzerland

  3:55-4:15 A Faster Algorithm for Minimum Cost Submodular Flows

  Satoru Iwata, Osaka University, Japan; S. Thomas McCormick, University of British Columbia, Canada; and Maiko Shigeno, Tokyo Institute of Technology, Japan

• Session 6

  3:05 PM-4:15 PM
  Chair: Vojta Rodl, Emory University
  Gold Rush B Room
  

  3:05-3:25 The Ultimate Interval Graph Recognition Algorithm?

  Derek G. Corneil, University of Toronto, Canada; Stephan Olariu, Old Dominion University; and Lorna Stewart, University of Alberta, Canada

  3:30-3:50 Sparse 0-1-Matrices and Forbidden Hypergraphs

  Claudia Bertram-Kretzberg and Thomas Hofmeister, Universit�t Dortmund, Germany; and Hanno Lefmann, Universit�t L�beck, Germany

  3:55-4:15 Fast Backtracking Principles Applied to Find New Cages

  Brendan McKay, Australian National University, Australia; Wendy Myrvold, University of Victoria, Canada; and Jacqueline Nadon, Sandwell Construction

4:15 PM-4:40 PM Coffee

4:40 PM-5:50 PM Concurrent Sessions

• Session 7

  4:40 PM-5:50 PM
  Chair: Yuval Rabani, Technion-Israel Institute of Technology, Israel
  Gold Rush A Room
  

  4:40-5:00 Approximation Algorithms for Directed Steiner Problems

  Moses Charikar and Chandra Chekuri, Stanford University; To-Yat Cheung and Zuo Dai, City University of Hong Kong; Ashish Goel and Sudipto Guha, Stanford University; and Ming Li, City University of Hong Kong

  5:05-5:25 Approximation Algorithms for Constraint Satisfaction Problems Involving at Most Three Variables Per Constraint

  Uri Zwick, Tel-Aviv University

  5:30-5:50 New Approximation Techniques for Some Ordering Problems

  Satish Rao, NEC Research Institute, Princeton; and Andrea W. Richa, Carnegie Mellon University

• Session 8

  4:40 PM-5:50 PM
  Chair: Aravind Srinivasan, National University of Singapore, Singapore
  Gold Rush B Room
  

  4:40-5:00 On the Distributed Complexity of Computing Maximal Matchings

  Michal Hanckowiak and Michal Kar�nski, Adam Mickiewicz University, Poland; and Alessandro Panconesi, Humboldt University, Germany

  5:05-5:25 The Power of Migration in Multi-Processor Scheduling of Real-Time Systems

  Gilad Koren, Netania College and Bar-Ilan University, Israel; Amihood Amir, Georgia Institute of Technology and Bar-Ilan University, Israel; and Emanuel Dar, Bar-Ilan Univeristy, Israel

  5:30-5:50 Computation in Noisy Radio Networks

  Eyal Kushilevitz, Technion-Israel Institute of Technology, Israel; and Yishay Mansour, Tel-Aviv University

Sunday Evening, January 25

Changed to Monday Evening, January 26
6:00 PM-7:00 PM
Business Meeting - SODA '99
Redwood Room

Monday Morning, January 26

7:30 AM-4:00 PM Registration
8:00 AM-8:50 AM Continental Breakfast

9:00 AM-10:35 AM Concurrent Sessions

• Session 9

  9:00 AM-10:35 AM
  Chair: Howard Karloff, Georgia Institute of Technology
  Gold Rush A Room
  

  9:00-9:20 A 3/2-Approximation Algorithm for Sorting by Reversals

  David A. Christie, The University of Glasgow, Scotland

  9:25-9:45 A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem

  Naveen Garg, Max-Planck-Institut f�r Informatik-Saarbr�cken, Germany; Goran Konjevod and R. Ravi, Carnegie Mellon University

  9:50-10:10 A New Approximation Algorithm for the Planar Augmentation Problem

  Sergej Fialko and Petra Mutzel, Max-Planck Institut f�r Informatik-Saarbr�cken, Germany

  10:15-10:35 Flow and Stretch Metrics for Scheduling Continuous Job Streams

  Michael Bender, Bell Laboratories, Lucent Technologies; Soumen Chakravarti, IBM Almaden Research Center; and S. Muthukrishnan, Bell Laboratories, Lucent Technologies

• Session 10

  9:00 AM-10:35 AM
  Chair: Jeremy Spinrad, Vanderbilt University
  Gold Rush B Room
  

  9:00-9:20 Optimal Augmentation of a Biconnected Graph to a k-Edge-Connected and Triconnected Graph

  Toshimasa Ishii, Hiroshi Nagamochi and Toshihide Ibaraki, Kyoto University, Japan

  9:25-9:45 Average-Case Analyses of First Fit and Random Fit Bin Packing

  Susanne Albers, Max-Planck-Institut fur Informatik-Saarbrucken, Germany; and Michael Mitzenmacher, Digital Equipment Corporation

  9:50-10:10 A Probabilistic Algorithm for Updating Files over a Communication Link

  Alexandre V. Evfimievski, Moscow State University, Russia

  10:15-10:35 Edge-Connectivity Augmentation with Partition Constraints

  Jorgen Bang-Jensen, Odense University, Denmark; Harold N. Gabow, University of Colorado, Boulder; Tibor Jordan, Odense University, Denmark; and Zoltan Szigeti, Universite Paris VI, France

10:35 AM-11:00 AM Coffee

11:00 AM-12:35 PM Concurrent Sessions

• Session 11

  11:00 AM-12:35 PM
  Chair: Amos Fiat, Tel-Aviv University, Israel
  Gold Rush A Room
  

  11:00-11:20 Exploring Unknown Undirected Graphs

  Petrisor Panaite and Andrzej Pelc, Universit� du Quebec a Hull, Canada

  11:25-11:45 On-line Randomized Call Control Revisited

  Stefano Leonardi, Max-Planck-Institut f�r Informatik-Saarbr�cken, Germany and Universit� di Roma "La Sapienza", Italy; Alberto Marchetti-Spaccamela and Alessio Presciutti, Universit� di Roma "La Sapienza", Italy; and Adi Ros�n, University of Toronto, Canada

  11:50-12:10 Ring Routing and Wavelength Translation

  Gordon Wilfong and Peter Winkler, Bell Laboratories, Lucent Technologies

  12:15-12:35 Direct Routing on Trees

  Stephen Alstrup, Jacob Holm, Kristian de Lichtenberg and Mikkel Thorup, University of Copenhagen, Denmark

• Session 12

  11:00 AM-12:35 PM
  Chair: Claire Kenyon, LRI, Université de Paris-Sud, France
  Gold Rush B Room
  

  11:00-11:20 Faster Random Generation of Linear Extensions

  Russ Bubley and Martin Dyer, University of Leeds, United Kingdom

  11:25-11:45 Beating the 2\delta Bound for Approximately Counting Colourings: A Computer-Assisted Proof of Rapid Mixing

  Russ Bubley, Martin Dyer and Catherine Greenhill, University of Leeds, United Kingdom

  11:50-12:10 Analysis of Random Processes via And-Or Tree Evaluation

  Micahel G. Luby and Michael Mitzenmacher, Digital Equipment Corporation; and M. Amin Shokrollahi, Universit�t Bonn, Germany

  12:15-12:35 Output-Sensitive Generation of Random Events

  Paul B. Callahan, Eidgenossische Technische Hochschule-Zurich, Switzerland

Monday Afternoon, January 26

12:35 PM-2:00 PM Lunch (attendees are on their own)

IP2
Factoring: Facts and Fables

2:00 PM-3:00 PM
Chair: Amos Fiat, Tel-Aviv University, Israel
Gold Rush A Room

In theory, the security of most Public Key Cryptosystems is based on the assumption that a number theoretical problem (such as integer factorization or computing discrete logarithms) is hard. In practice, when using Public Key Cryptosystems, to secure Internet traffic for instance, the situation is not so clear. In this talk the speaker will discuss various security assumptions and will show how our credulity may lead to interesting business opportunities.

Arjen K. Lenstra
Citibank, N.A.,
Parsippany, NJ

3:05 PM-4:15 PM Concurrent Sessions

• Session 13

  3:05 PM-4:15 PM
  Chair: Nati Linial, Hebrew University
  Gold Rush A Room
  

  3:05-3:25 On Approximating Rectangle Tiling and Packing

  Sanjeev Khanna and S. Muthukrishnan, Bell Laboratories, Lucent Technologies; and Mike Paterson, University of Warwick, United Kingdom

  3:30-3:50 The Maximum Subforest Problem: Approximation and Exact Algorithms

  Ron Shamir and Dekel Tsur, Tel-Aviv University, Israel

  3:55-4:15 Matroid Decomposition Methods for the Set Maxima Problem

  Vincenzo Liberatore, Rutgers University

• Session 14

  3:05 PM-4:15 PM
  Chair: Yuval Rabani, Technion-Israel Institute of Technology, Israel
  Gold Rush B Room
  

  3:05-3:25 The Dynamic Servers Problem

  Moses Charikar, Stanford University; Dan Halperin, Tel-Aviv University, Israel; and Rajeev Motwani, Stanford University

  3:30-3:50 Bounding the Diffuse Adversary

  Neal E. Young, Dartmouth College

  3:55-4:15 Ancient and New Algorithms for Load Balancing in the Lp Norm

  Adi Avidor and Yossi Azar, Tel-Aviv University, Israel; and Jiri Sgall, Mathematical Institute, Czech Republic

4:15 PM-4:40 PM Coffee

4:40 PM-5:50 PM Concurrent Sessions

• Session 15

  4:40 PM-5:50 PM
  Chair: Jeremy Spinrad, Vanderbilt University
  Gold Rush A Room
  

  4:40-5:00 Optimal Edge Ranking of Trees in Linear Time

  Tak Wah Lam, University of Hong Kong; and Fung Ling Yue, City University of Hong Kong

  5:05-5:25 Algorithms for the Maximum Subarray Problem Based on Matrix Multiplication

  Hisao Tamaki, Meiji University, Japan; and Takeshi Tokuyama, Tokyo Research Laboratory, Japan

  5:30-5:50 An Experimental Study of Linear Programming-Based Approximation Algorithms for Scheduling Problems

  Martin W. P. Savelsbergh, Georgia Institute of Technology; R. N. Uma and Joel Wein, Polytechnic University

• Session 16

  4:40 PM-5:50 PM
  Chair: Hal Kierstead, Arizona State University
  Gold Rush B Room
  

  4:40-5:00 Approximate String Matching: A Simpler Faster Algorithm

  Richard Cole, Courant Institute of Mathematical Sciences, New York University; and Ramesh Hariharan, Indian Institute of Science, India

  5:05-5:25 Fast Distributed Algorithms for Brooks-Vizing Colourings

  David A. Grable and Alessandro Panconesi, Humboldt-Universit�t zu Berlin, Germany

  5:30-5:50 Mutual Search

  Harry Buhrman, Centrum voor Wiskunde en Informatica, The Netherlands; Matthew Franklin, AT&T Research; Juan A. Garay, IBM T. J. Watson Research Center; Jaap-Henk Hoepman, John Tromp and Paul Vitanyi, Centrum voor Wiskunde en Informatica, The Netherlands

Monday Evening, January 26

6:00 PM-7:00 PM
Business Meeting - SODA '99
Redwood Room

Tuesday Morning, January 27

7:30 AM-2:00 PM Registration

8:00 AM-8:50 AM Continental Breakfast

9:00 AM-10:35 AM Concurrent Sessions

• Session 17

  9:00 AM-10:35 AM
  Chair: Andrew Goldberg, NEC Research Institute
  Gold Rush A Room
  

  9:00-9:20 Better Random Sampling Algorithms for Flows in Undirected Graphs

  David Karger, Massachusetts Institute of Technology

  9:25-9:45 Augmenting Undirected Edge Connectivity in O (n squared) Time

  Andras Benczur and David Karger, Massachusetts Institute of Technology

  9:50-10:10 Go With the Winners for Graph Bisection

  Tassos Dimitriou and Russell Impagliazzo, University of California, San Diego

  10:15-10:35 Two New Upper Bounds for SAT

  Edward A. Hirsch, Steklov Institute of Mathematics, Russian Academy of Sciences, Russia

• Session 18

  9:00 AM-10:35 AM
  Chair: Rao Kosaraju, Johns Hopkins University
  Gold Rush B Room
  

  9:00-9:20 The Analysis of Hybrid Trie Structures

  Julien Cl�ment, INRIA-Rocquencourt, France and Universit� de Caen, France; Philippe Flajolet, INRIA-Rocquencourt, France; and Brigitte Vallee, Universit� de Caen, France

  9:25-9:45 Finger Search Trees with Constant Insertion Time

  Gerth S. Brodal, Max-Planck-Institut fur Informatik-Saarbrucken, Germany

  9:50-10:10 Faster Deterministic Sorting and Priority Queues in Linear Space

  Mikkel Thorup, University of Copenhagen, Denmark

  10:15-10:35 Error Correcting Codes, Perfect Hashing Circuits, and Deterministic Dynamic Dictionaries

  Peter Bro Miltersen, University of Aarhus, Denmark

10:35 AM-11:00 Coffee

11:00 AM-12:35 PM Concurrent Sessions

• Session 19

  11:00 AM-12:35 PM
  Chair: Sampath Kannan, University of Pennsylvania
  Gold Rush A Room
  

  11:00-11:20 On Local Register Allocation

  Martin Farach and Vincenzo Liberatore, Rutgers University

  11:25-11:45 Linear-time Register Allocation For a Fixed Number of Registers

  Hans Bodlaender, University of Utrecht, The Netherlands; Jens Gustedt, Technische Universit�t Berlin, Germany; and Jan Arne Telle, Universiteit Bergen, Norway

  11:50-12:10 Multi-Item Inventory Staggering Problems: Heuristics and Bounds

  Chung-Piaw Teo, Jihong Ou and Kok-Choon Tan, National University of Singapore, Singapore

  12:15-12:35 Finding a Large Hidden Clique in a Random Graph

  Noga Alon, Michael Krivelevich and Benny Sudakov, Tel-Aviv University, Israel

• Session 20

  11:00 AM-12:35 PM
  Chair: Marshall Bern, Xerox Palo Alto Research Center
  Gold Rush B Room
  

  11:00-11:20 Learning Deterministic Finite Automata from Smallest Counterexamples

  Andreas Birkendorf, Andreas Boeker and Hans Ulrich Simon, Universit�t Dortmund, Germany

  11:25-11:45 On the Exact Worst Case Complexity of Planar Point Location

  Udo Adamy and Raimund Seidel, Universit�t des Saarlandes, Germany

  11:50-12:10 Fast Hierarchical Clustering and Other Applications of Dynamic Closest Pairs

  David Eppstein, University of California, Irvine

  12:15-12:35 Analysis of First-Come-First-Serve Parallel Job Scheduling

  Uwe Schwiegelshohn and Ramin Yahyapour, Universit�t Dortmund, Germany

Tuesday Afternoon, January 27

12:35 PM-2:00 PM Lunch (attendees are on their own)

IP3
Four Decades of Optimal Network Design

2:00 PM-3:00 PM
Chair: David Shmoys , Cornell University
Gold Rush A Room

The optimal design of telecommunication and other networks poses considerable modeling and algorithmic challenges to the applied mathematics, computer science, and operations research communities. In this problem domain, (mixed) integer programming models often contain thousands or even millions of variables and constraints. The speaker will trace the evolution of optimization methods for network design, reviewing some major developments, including the design and analysis of heuristics, Lagrangian relaxation, dual ascent methods, and polyhedral combinatorics. He will also summarize several applications and suggest some open research issues as well as attempt to suggest why network design remains among the most computationally elusive of all combinatorial optimization problems and continues to pose significant challenges to the research community.

Thomas L. Magnanti
Operations Research Center
Massachusetts Institute of Technology

3:05 PM-4:40 PM Concurrent Sessions

• Session 21

  3:05 PM-4:40 PM
  Chair: Daniel Spielman, Massachusetts Institute of Technology
  Gold Rush A Room
  

  3:05-3:25 Spatial Codes and the Hardness of String Folding Problems

  Ashwin Nayak and Alistair Sinclair, University of California, Berkeley; and Uri Zwick, Tel-Aviv University, Israel

  3:30-3:50 Greedy Strikes Back: Improved Facility Location Algorithms

  Sudipto Guha, Stanford University; and Samir Khuller, University of Maryland, College Park

  3:55-4:15 Exact and Approximation Algorithms for Clustering

  Pankaj K. Agarwal and Cecilia M. Procopiuc, Duke University

  4:20-4:40 Authoritative Sources in a Hyperlinked Environment

  Jon M. Kleinberg, Cornell University

• Session 22

  3:05 PM-4:15 PM
  Chair: Nati Linial, Hebrew University, Israel
  Gold Rush B Room
  

  3:05-3:25 Hiding Cliques for Cryptographic Security

  Ari Juels, RSA Laboratories, Bedford, Massachusetts; and Marcus Peinado, German National Research Center for Information Technology, Germany

  3:30-3:50 Theory and Practice of I/O-Efficient Algorithms for Multidimensional Batched Searching Problems

  Lars Arge and Octavian Procopiuc, Duke University; Sridhar Ramaswamy and Torsten Suel, Bell Laboratories, Lucent Technologies; and Jeffrey Scott Vitter, Duke University

  3:55-4:15 Identification of Gene Regulatory Networks by Strategic Gene Disruptions and Gene Overexpressions

  Tatsuya Akutsu, University of Tokyo, Japan; Satoru Kuhara, Kyushu University, Japan; Osamu Maruyama and Satoru Miyano, University of Tokyo, Japan

4:40 PM Conference adjourns

SODA'98 Homepage | Program Updates| Registration | Hotel | Transportation | Program-at-a-Glance | Author Index |