• Conference Topics
• Deadlines
• Program Committee
• Technical Program
• Hotel Information
  • Hotel Roommate-Sharing Database
  • Hotel Reservation Form
• Transportation Information
  • by air
  • car rental
  • shuttles to the hotel
  • driving directions
• Symposium Registration
  • Preregistration Form

This page is under construction.

Conference Topics

• Pankaj K. Agarwal
  Duke University

  Mikhail Atallah

  Purdue University, West Lafayette

  Kenneth Clarkson (chair)

  AT&T Bell Laboratories

  Alan Frieze

  Carnegie Mellon University

  Andrew Goldberg

  Stanford University

  Howard Karloff

  Georgia Institute of Technology

  Udi Manber

  University of Arizona

  Ian Munro

  University of Waterloo, Canada

  Prabhakar Raghavan

  IBM Thomas J. Watson Research Center

  Jeanette Schmidt

  Polytechnic University

  Moti Yung

  IBM Thomas J. Watson Research Center

Saturday, January 21, 1995

Sunday Morning, January 22

8:30

Design of Practical and Provably Good Random Number Generators

Bill Aiello, Bellcore; S. Rajagopalan, Boston University; and Ramarathnam Venkatesan, Bellcore

8:55

On the Statistical Dependencies of Coalesced Hashing and Their Implications for Both Full and Limited Randomness

Alan Siegel, Courant Institute of Mathematical Sciences, New York University

9:20

On-line Approximate List Indexing with Applications

Arne Andersson, Lund University, Sweden; and Ola Petersson, Lund University, Sweden and Vaxjo University, Sweden

9:45

Selecting the Median

Dorit Dor and Uri Zwick, Tel Aviv University, Israel

8:30

Chaining Multiple-Alignment Fragments in Sub-Quadratic Time

Gene Myers, University of Arizona; and Webb Miller, Pennsylvania State University

8:55

On the Entropy of DNA: Algorithms and Measurements based on Memory and Rapid Convergence

Martin Farach and Michiel Noordewier, Rutgers University; Serap Savari, Massachusetts Institute of Technology; Larry Shepp, AT&T Bell Laboratories; Abraham Wyner, Stanford University; and Jacob Ziv, Technion-Israel Institute of Technology, Israel

9:20

Improved Algorithms for Protein Motif Recognition

Bonnie Berger, and David B. Wilson, Massachusetts Institute of Technology

9:45

Computing the Local Consensus of Trees

Sampath K. Kannan, University of Arizona; Tandy Warnow and Shibu Yooseph, University of Pennsylvania

Sunday Afternoon, January 22

1:15

Polynomial Methods for Separable Convex Optimization in Unimodular Spaces

Alexander V. Karzanov, Institute for System Analysis, Russia and S. Thomas McCormick, University of British Columbia, Canada

1:40

Covering and Packing Algorithms for Graphic Polymatroids

Harold N. Gabow, University of Colorado, Boulder

2:05

A Combinatorial Algorithm for Minimizing Symmetric Submodular Functions

Maurice Queyranne, University of British Columbia, Canada

2:30

From Valid Inequalities to Heuristics: A Unified View of

Primal-dual Approximation Algorithms in Covering Problems Dimitris Bertsimas and Chung-Piaw Teo, Massachusetts Institute of Technology

1:15

Doing Two-Level Logic Minimization 100 Times Faster

Olivier Coudert, DEC Paris Research Laboratory, France

1:40

Finding Optimal Edge-Rankings of Trees

Xiao Zhou and Takao Nishizeki, Tohoku University, Japan

2:05

Efficient Parallel Computations for Singular Band Matrices

Wayne Eberly, University of Calgary, Canada

2:30

External-Memory Graph Algorithms

Yi-Jen Chiang, Brown University; Michael T. Goodrich, Johns Hopkins University; Edward F. Grove, Duke University; Roberto Tamassia, Brown University; Darren Erik Vengroff and Jeffrey Scott Vitter, Duke University

3:30

Finding Subsets Maximizing Minimum Structures

Magnus M. Halldorsson, Japan Advanced Institute of Science and Technology, Japan; Kazuo Iwano, IBM Tokyo Research Laboratory, Japan; Naoki Katoh, Kobe University of Commerce, Japan; and Takeshi Tokuyama, IBM Tokyo Research Laboratory, Japan

3:55

Approximating Discrete Collections via Local Improvements

Magnus M. Halldorsson, Japan Advanced Institute of Science and Technology, Japan

4:20

Randomized Rounding Without Solving the Linear Program

Neal E. Young, Cornell University

4:45

Average Case Analysis of Dynamic Graph Algorithms

David Alberts, Freie Universitat Berlin, Germany; and Monika Rauch Henzinger, Cornell University

3:30

Dihedral Bounds for Mesh Generation in High Dimensions

Marshall Bern, Xerox Palo Alto Research Center; Paul Chew, Cornell University; David Eppstein, University of California, Irvine; and Jim Ruppert, IBM Almaden Research Center

3:55

Voronoi Diagrams of Lines in 3-Space Under Polyhedral Convex Distance Functions

L. Paul Chew, Cornell University; Klara Kedem, Ben Gurion University, Israel and Cornell University; Micha Sharir, Tel Aviv University, Israel and Courant Institute of Mathematical Sciences, New York University; Boaz Tagansky, Tel Aviv University, Israel; and Emo Welzl, Freie Universitat Berlin, Germany and International Computer Science Institute, Berkeley

4:20

Multiple Translational Containment: Approximate and Exact Algorithms

Karen Daniels and Victor Milenkovic, Harvard University

4:45

A New Way to Weigh Malnourished Euclidean Graphs

Gautam Das and Giri Narasimhan, University of Memphis; and Jeffrey Salowe, QuesTech, Inc., Falls Church, VA

Monday Morning, January 23

8:30

Path Optimization and Near-Greedy Analysis for Graph Partitioning: An Empirical Study

Jonathan Berry and Mark Goldberg, Rensselaer Polytechnic Institute

8:55

On the Performance of Spectral Graph Partitioning Methods

Stephen Guattery and Gary L. Miller, Carnegie Mellon University

9:20

Guaranteeing Fair Service to Persistent Dependent Tasks

Amotz Bar-Noy, IBM T.J. Watson Research Center; Alain Mayer, Columbia University; Baruch Schieber and Madhu Sudan, IBM T.J. Watson Research Center

9:45

Adapted Diameters and the Efficient Computation of Fourier Transforms of Finite Groups

David K. Maslen, Max-Planck-Institut fur Informatik, Germany; and Daniel N. Rockmore, Dartmouth College

8:30

Algorithms for Dynamic Closest-Pair and n-Body Potential Fields

Paul B. Callahan and S. Rao Kosaraju, Johns Hopkins University

8:55

Circular Separability of Polygons

Jean-Daniel Boissonnat, INRIA, France; Jurek Czyzowicz, Universite du Quebec a Hull, Canada; Olivier Devillers and Mariette Yvinec, INRIA, France

9:20

Output-Sensitive Construction of Polytopes in Four Dimensions and Clipped Voronoi Diagrams in Three

Timothy M. Chan and Jack Snoeyink, University of British Columbia, Canada; and Chee-Keng Yap, Courant Institute of Mathematical Sciences, New York University

9:45

On the All-Pairs Euclidean Short Path Problem

Danny Z. Chen, University of Notre Dame

10:10-10:45

Nikko I

Coffee Break

10:45-11:45

Invited Presentation 2/Nikko II

Algorithmic Problems Arising in Speech Recognition

Fernando C. Pereira, AT&T Bell Laboratories

11:45 AM-1:15 PM

Grey Pearl 1&2

Lunch

Monday Afternoon, January 23

1:15

Locally Orientable Graphs, Cell Structures, and a New Algorithm for the Incremental Maintenance of Connectivity Carcasses

Yefim Dinitz, Technion-Israel Institute of Technology, Israel; and A. Vainshtein, Tel Aviv University, Israel

1:40

Average-Case Analysis of Off-Line and On-Line Knapsack Problems

George S. Lueker, University of California, Irvine

2:05

An Analysis of Some Heuristics for the Maximum Planar Subgraph Problem

Robert J. Cimikowski, Montana State University

2:30

An Approximation Algorithm for Minimum-Cost Vertex- Connectivity Problems

R. Ravi, University of California, Davis; and David P. Williamson, Cornell University

1:15

Algorithms for the Optimal Loading of Recursive Neural Nets

V. Chandru, A. Dattasharma and S.S. Keerthi, Indian Institute of Science, India; N.K. Sancheti, Motorola India, India; and V. Vinay, Centre for AI and Robotics, India

1:40

Using Network Flows for Surface Modeling

Rolf H. Mohring, Matthias Mueller-Hannemann and Karsten Weihe, Technische Universitat Berlin, Germany

2:05

Register Allocation in Structured Programs

Sampath Kannan and Todd Proebsting, University of Arizona

2:30

Lower Bounds for Identifying Subset Members with Subset Queries

Emanuel Knill, Los Alamos National Laboratory

2:55-3:30

Nikko I

Coffee Break

3:30

The P-range Tree: A New Data Structure for Range Searching in Secondary Memory

Sairam Subramanian and Sridhar Ramaswamy, Brown University

3:55

Lower Bounds for Linear Satisfiability Problems

Jeff Erickson, University of California, Berkeley

4:20

Morphing Binary Trees

John Hershberger, Mentor Graphics, San Jose, CA; and Subhash Suri, Washington University

4:45

Computing a Minimum-weight k-link Path in Graphs with the Concave Monge Property

Baruch Schieber, IBM T.J. Watson Research Center

3:30

Improved Randomized On-Line Algorithms for the List Update Problem

Susanne Albers, International Computer Science Institute

3:55

On Algorithm Design for Metrical Task Systems

William R. Burley, University of California, San Diego; and Sandy Irani, University of California, Irvine

4:20

On-line Bin Packing with Lookahead

Edward F. Grove, Duke University

4:45

Localizing a Robot with Minimum Travel

Gregory Dudek, Kathleen Romanik and Sue Whitesides, McGill University, Canada

Tuesday Morning, January 24

8:30

Approximating Shortest Paths on a Convex Polytope in R3

John Hershberger, Mentor Graphics, San Jose, CA; and Subhash Suri, Washington University

8:55

Trustee-based Tracing Extensions to Anonymous Cash and the Making of Anonymous Change

Ernie Brickell, Peter Gemmell and David Kravitz, Sandia National Laboratories, Albuquerque

9:20

The Statistical Adversary Allows Optimal Money-Making Trading Strategies

Andrew Chou, Massachusetts Institute of Technology; Jeremy Cooperstock and Ran El-Yaniv, University of Toronto, Canada; Michael Klugerman and Frank Thomson Leighton, Massachusetts Institute of Technology

9:45

Fairness in Scheduling

Miklos Ajtai, IBM Almaden Research Center; James Aspnes, Yale University; Moni Naor, Weizmann Institute of Science, Israel; Yuval Rabani, Massachusetts Institute of Technology; Leonard J. Schulman, University of California, Berkeley; and Orli Waarts, IBM Almaden Research Center

8:30

Fast Deterministic Approximation for the Multicommodity Flow Problem

Tomasz Radzik, King's College London, United Kingdom

8:55

Fast Approximation Algorithm for Minimum Cost Multicommodity Flow

Anil Kamath, Omri Palmon and Serge Plotkin, Stanford University

9:20

Improved Interior Point Algorithms for Exact and Approximate

Solution of Multicommodity Flow Problems Anil Kamath and Omri Palmon, Stanford University

9:45

The Quickest Transshipment Problem

Bruce Hoppe and Eva Tardos, Cornell University

Tuesday Afternoon, January 24

1:15

Splay Tree for Data Compression

Dennis Grinberg, Carnegie Mellon University; Sivaramakrishnan Rajagopalan, Boston University; Ramarathnam Venkatesan, and Victor K. Wei, Bellcore

1:40

Fast Incremental Text Editing

Paolo Ferragina, Universita di Pisa, Italy; and Roberto Grossi, Universita di Firenze, Italy

2:05

Parameterized Pattern Matching by Boyer-Moore-type Algorithms

Brenda S. Baker, AT&T Bell Laboratories

2:30

Counting and Random Generation of Strings in Regular Languages

Sampath K. Kannan, University of Arizona; Z. Sweedyk, University of California, Berkeley; and Steve Mahaney, DIMACS, Rutgers University

1:15

Greedy Dynamic Routing on Arrays

Nabil Kahale, Xerox Palo Alto Research Center; and Frank Thomson Leighton, Massachusetts Institute of Technology

1:40

Improved Bounds for All Optical Routing

Yonatan Aumann and Yuval Rabani, Massachusetts Institute of Technology

2:05

Broadcast in Radio Networks

Iris Gaber and Yishay Mansour, Tel Aviv University, Israel

2:30

Optimal One-Way Sorting on a One-Dimensional Sub-Bus Array

James D. Fix and Richard E. Ladner, University of Washington

3:30

A Fast Algorithm for the Computation and Enumeration of

Perfect Phylogenies when the Number of Character States is Fixed Sampath Kannan, University of Arizona; and Tandy Warnow, University of Pennsylvania

3:55

Of Mice and Men: Evolutionary Distances between Genomes under Translocation

John D. Kececioglu and R. Ravi, University of California, Davis

4:20

Sorting by Transpositions

Vineet Bafna and Pavel A. Pevzner, Pennsylvania State University

3:30

Graph Isomorphism Testing without Numerics for Graphs of Bounded Eigenvalue Multiplicity

Martin Fuerer, Pennsylvania State University

3:55

Subgraph Isomorphism in Planar Graphs and Related Problems

David Eppstein, University of California, Irvine

4:20

Characterizations of k-Terminal Flow Networks and Computing Network Flows in Partial k-Trees

Torben Hagerup, Max-Planck-Institut fur Informatik, Germany; Jyrki Katajainen, Kobenhavns Universitet, Denmark; Naomi Nishimura and Prabhakar Ragde, University of Waterloo, Canada

Conference Adjourns

Location

Deposit

Arrivals and Departures

Cancellations

Dining

There are also one or two online restaurant review sources.

Recreational Facilities

Parking

Telephone Messages

SIAM will keep a database of attendees who may wish to share a room with another attendee at the conference to cut down on expenses. To be placed on this database, you must forward the following information via e-mail to: degiulio@siam.org or by fax: 215-386-7999. Be sure to specify that you want to be placed on the SODA database.

Name

Address

Phone, Fax and E-mail

Gender

Smoker/Non-Smoker

Arrival/Departure Dates

It is the responsibility of the attendee to make the contacts and arrangements with attendees on the database.

in plain text

By Air

SIAM has selected Get-A-Way Travel agency to assist attendees in making travel arrangements. Get-A-Way Travel will make your reservations on USAir or any airline of your choice. To take advantage of the USAir discounts, you must book your reservation through Get-A-Way Travel by calling 1-800-223-3863 or 215-379-6800. Ask for Carol Brecht. Be sure to mention that you are attending the ACM/SIAM Symposium on Discrete Algorithms (SODA). Get-A-Way Travel will issue your tickets and mail them to you.

Car Rental

Type of Car            Daily Rate     Weekly Rate
                       (1-4 days)     (5-7 days)

Compact                $31.00         $155
Intermediate           $34.00         $170
Standard               $35.00         $175
Luxury                 $44.00         $220
MiniVan                $45.00         $225

Additional charges: 
$9.00/day   Loss Damage Waiver
$4.95/day   Personal Accident Insurance & Personal Effects
            Protection Protect.           
$7.95/day   Supplemental Liability

Reservations

• Cars must be picked up and returned to the same location.
• You must be at least 25 years of age and have a valid U.S. or International Drivers License.
• You must have one of the following credit cards to rent a car: American Express, MasterCard, or VISA.
• Refueling charges, collision insurance, and taxes are not included in the above rates.

On occasion, the car rental agency may offer special rates that are lower than rates quoted above. As an attendee, you are eligible for the lower of the two rates. In most instances, the symposium discount rates are lower than those quoted to the general public.

Airport Transportation

Symposium Registration

Saturday, January 21     6:00 PM - 8:00 PM 
Sunday, January 22       8:30 AM - 4:00 PM
Monday, January 23       8:30 AM - 4:00 PM
Tuesday, January 24      8:30 AM - 1:30 PM

REGISTRATION FEES
Preregistration deadline:   Monday, January 9, 1995.

                                    ACM/SIAM          Non-
                                    Member            Member    Student
Preregistration: before 1/9/95                  
                                    $270              $320        $ 75
After 1/9/94                        $320              $370        $125

Fees includes proceedings which will be available at the symposium welcoming reception and daily lunch.

To register, complete the Preregistration Form and send it with your payment to SIAM. You can also register in the following ways:

• Telephone: 215-382-9800; Toll free: 800-447-7426 (USA only).
• email: meetings@siam.org
• Fax: 215-386-7999

We urge attendees to preregister and save! To qualify for the preregistration fee, the Preregistration Form and payment must be received at the SIAM Office by Monday, January 9, 1995.

Preregistration received at the SIAM office after Monday, January 9, will be subject to the difference between the preregistration and the on-site registration fees. The difference will be charged to your credit card or collected from you on-site.

There will be no prorated fees. No refunds will be issued after Saturday, January 21, 1995.

On-site registration begins on Saturday, January 21, 1995. If your preregistration payment arrives at SIAM after the conference has started, that payment will returned to you. Your on-site registration will be processed.

Cancellation policy

Cancellation prior to:              

      January 9, 1995                   Full refund
      January 10 - 21, 1995              $25.00 Cancellation Fee
      After January 21, 1995             No Refund

Credit Cards

SIAM accepts VISA, MasterCard and American Express. Please indicate credit card type, account number and the expiration date on the Preregistration Form.

in plaintext