dsj@RESEARCH.ATT.COM (David Johnson) (11/26/90)
Second Annual ACM-SIAM Symposium on Discrete Algorithms
January 28-30, 1991
Cathedral Hill Hotel
San Francisco, CA
The symposium will be held in the International Ballroom of
the Cathedral Hill Hotel, Van Ness at Geary Street, San
Francisco, CA. Coffee will be served in the Mezzanine, and
lunches will be served in the Eldorado Room.
Sunday, January 27
Registration opens: 6:00 PM-9:00 PM
Session 1: 8:40 AM - 10:40 AM (Monday, January 28)
8:40 Maintaining the Minimal Distance of a Point Set in
Polylogarithmic Time Michiel Smid, Universitat des Saarlandes, Germany
9:00 Space-efficient Ray-shooting and Intersection
Searching: Algorithms, Dynamization, and Applications Siu Wing Cheng and
Ravi Janardan, University of Minnesota,
Minneapolis
9:20 Approximation Algorithms for Planar Traveling Salesman
Tours and Minimum-Length Triangulations
Kenneth L. Clarkson, AT&T Bell Laboratories
9:40 Finding Stabbing Lines in 3-Dimensional Space
Marco Pellegrini, New York University, Courant Institute of
Mathematical Sciences and Peter W. Shor, AT&T Bell
Laboratories
10:00 Offline Maintenance of Planar Configurations
John Hershberger, DEC Systems Research Center and Subhash
Suri, Bell Communications Research
10:20 Matching Points into Noise Regions: Combinatorial
Bounds and Algorithms
Esther M. Arkin, Cornell University; Klara Kedem, Tel Aviv
University, Israel; Joseph S.B. Mitchell, Cornell University;
Josef Sprinzak and Michael Werman, Hebrew University, Israel
10:40 AM-11:00 AM Coffee Break
11:00 AM-12:00 PM Invited Presentation 1
"Molecular Biology and Computer Science: Ideas and Algorithms"
Eric S. Lander, Whitehead Institute for Biomedical Research, and
Massachusetts Institute of Technology 12:00 PM-1:30 PM Lunch Break
Session 2: 1:30 PM-3:30 PM (Monday, January 28)
1:30 Dynamic Expression Trees and Their Applications
Robert F. Cohen and Roberto Tamassia, Brown University
1:50 On Partitions and Presortedness of Sequences
Jingsen Chen and Svante Carlsson, Lund University, Sweden
2:10 Adaptive Heuristics for Binary Search Trees and Constant
Linkage Cost
Tony W. Lai and Derick Wood, University of Waterloo, Canada
2:30 Persistence, Amortization and Randomization
Paul F. Dietz and Rajeev Raman, University of Rochester
2:50 Fully Persistent Lists with Catenation
James R. Driscoll, Dartmouth College; Daniel D.K. Sleator,
Carnegie Mellon University; and Robert E. Tarjan, Princeton
University
3:10 The Analysis of Multidimensional Searching in Quad-Trees
Philippe Flajolet, INRIA, Rocquencourt, France; Gaston
Gonnet, ETH, Switzerland; Claude Puech, ENS, Paris, France;
and Mike Robson, Australian National University, Australia
3:30 PM-3:50 PM Coffee Break
Session 3: 3:50 PM-5:50 PM (Monday, January 28)
3:50 A Strongly Polynomial Minimum Mean Cut Cancelling
Algorithm for Submodular Flow
S. Thomas McCormick, University of British Columbia, Canada
4:10 Tight Bounds on the Number of Minimum-Mean Cycle Cancellations
Tomasz Radzik and Andrew V. Goldberg, Stanford University
4:30 On the Complexity of Some Flow Problems
Edith Cohen, Stanford University and IBM Almaden Research
Center, and Nimrod Megiddo, IBM Almaden Research Center and
Tel Aviv University, Israel
4:50 Recognizing Strong Connectivity in Periodic Graphs and
Its Relation to Integer Programming
Muralidharan Kodialam and James B. Orlin, Massachusetts
Institute of Technology
5:10 Complexity Results and Algorithms for {=,<,<=}-Constrained
Scheduling
Bonnie Berger and Lenore Cowen, Massachusetts Institute of
Technology
5:30 Improved Approximation Algorithms for Shop Scheduling Problems
David B. Shmoys, Cornell University; Clifford Stein and
Wein, Massachusetts Institute of Technology Tuesday Morning, January 29
Session 4: 8:40 AM-10:40 AM (Tuesday, January 29)
8:40 Efficient Sequential and Parallel Algorithms for
Computing Recovery Points in Trees and Paths
Marek Chrobak, University of California, Riverside; David
Eppstein, Xerox PARC and University of California, Irvine;
Giuseppe F. Italiano, Columbia University and Universita di
Roma "La Sapienza", Italy; and Moti Yung, IBM Thomas J.
Watson Research Center
9:00 Optimal Algorithms for Partitioning Trees
Greg N. Frederickson, Purdue University, West Lafayette
9:20 On Finding Minimal Two-Connected Subgraphs
Pierre Kelsen and Vijaya Ramachandran, University of Texas, Austin
9:40 A Sublinear Randomized Parallel Algorithm for the
Maximum Clique Problem in Perfect Graphs
Farid Alizadeh, University of Minnesota, Minneapolis
10:00 Edge Coloring Planar Graphs with Two Outerplanar Subgraphs
Lenwood S. Heath, Virginia Polytechnic Institute and State
University
10:20 Upward Planar Drawing of Single Source Acyclic Digraphs
Michael Hutton and Anna Lubiw, University of Waterloo, Canada
10:40 AM-11:00 AM Coffee Break
11:00 AM-12:00 PM Invited Presentation 2
"How Much of the Future is Worth Knowing?"
Ronald L. Graham, AT&T Bell Laboratories
12:00 PM-1:30 PM Lunch Break
Session 5: 1:30 PM-3:30 PM (Tuesday, January 29)
1:30 Efficient 2-Dimensional Approximate Matching of
Non-rectangular Figures
Amihood Amir and Martin Farach, University of Maryland,
College Park
1:50 Tight Bounds on the Complexity of the Boyer-Moore
String Matching Algorithm
Richard Cole, Courant Institute of Mathematical Sciences, New
York University
2:10 On-Line Weighted Matching
Bala Kalyanasundaram and Kirk Pruhs, University of Pittsburgh
2:30 On-Line Caching as Cache Size Varies
Neal E. Young, Princeton University
2:50 Randomized Competitive Algorithms for the List Update Problem Sandy
Irani, University of California, Berkeley; Nick
Reingold and Jeffery Westbrook, Yale University, and Daniel
Sleator, Carnegie Mellon University
3:10 The Canadian Traveller Problem
Amotz Bar-Noy and Baruch Schieber, IBM Thomas J. Watson
Research Center
3:30 PM-3:50 PM Coffee Break
Session 6: 3:50 PM-5:50 PM (Tuesday, January 29)
3:50 Fast Hashing on PRAM
Joseph Gil, Hebrew University, Israel and Yossi Matias,
Tel Aviv University, Israel
4:10 A New Lower Bound Technique and Its Application
Prakash Ramanan, University of California, Santa Barbara
4:30 Learning the Fourier Spectrum of Probabilistic Lists and Trees
William Aiello and Milena Mihail, Bell Communications Research
4:50 Approximating the Number of Solutions of a GF[2] Polynomial
Marek Karpinski, University of Bonn, Germany, and
International Computer Science Institute, and Michael Luby,
International Computer Science Institute
5:10 The First Classical Ramsey Number for Hypergraphs Is Computed
Brendan D. McKay, Australian National University, Australia,
and Stanislaw P. Radziszowski, Rochester Institute of
Technology
5:30 Bounded Space On-Line Bin Packing: Best is Better than First
J. Csirik, Bolyai Institute, Hungary, and David S. Johnson,
AT&T Bell Laboratories Wednesday Morning, January 30
Session 7: 8:40 AM - 10:40 AM (Wednesday, January 30)
8:40 Decomposing Graphs into Regions of Small Diameter
Nathan Linial, Hebrew University of Jerusalem, Israel, and
Michael Saks, University of California, San Diego
9:00 Density Graphs and Separators
Gary L. Miller, Carnegie Mellon University and University of
Southern California, and Stephen A. Vavasis, Cornell University
9:20 Triangulating Three-Colored Graphs
Sampath K. Kannan and Tandy J. Warnow, University of
California, Berkeley
9:40 Lower Bounds for On-Line Tree Embeddings
Panfeng Liu and David Greenberg, Yale University, and
Sandeep Bhatt, California Institute of Technology
10:00 Optimal Time Randomized Consensus--Making Resilient
Algorithms Fast in Practice
Michael Saks, University of California, San Diego, Nir
Shavit, IBM Almaden Research Center, and Heather Woll, University of
California, San Diego
10:20 An O( ) Time Algorithm for the 2-Chain Cover Problem
and Related Problems
Tze-heng Ma and Jeremy Spinrad, Vanderbilt University
10:40 AM-11:00 AM Coffee Break
11:00 AM-12:00 PM Invited Presentation 3
"Algorithmic Lattice Geometry"
Laszlo Lovasz, Princeton University, and Lorand Eotvos
University, Hungary
12:00 PM-1:30 PM Lunch
Session 8: 1:30 PM-3:30 PM (Wednesday, January 30)
1:30 The Fourth Moment Method
Bonnie Berger, Massachusetts Institute of Technology
1:50 Parallel Complexity of Tridiagonal Symmetric Eigenvalue
Problems
Dario Bini, Universita di Pisa, Italy; Victor Pan, Columbia
University, CUNY-Lehman College, and SUNY-Albany
2:10 An Efficient Parallel Algorithm for the Row Minima of a
Totally Monotone Matrix
Mikhail J. Atallah, Purdue University, West Lafayette, and
S. Rao Kosaraju, Johns Hopkins University
2:30 On the Parallel Complexity of Evaluating Game-Trees
Andrei Z. Broder and Anna R. Karlin, DEC Systems Research
Center, Prabhakar Raghavan, IBM Thomas J. Watson Research
Center, and Eli Upfal, IBM Almaden Research Center
2:50 Ultra-Fast Expected Time Parallel Algorithms Quentin F. Stout and
Philip D. MacKenzie, University of
Michigan, Ann Arbor
3:10 Time-Work Tradeoffs for Parallel Graph Algorithms
Thomas H. Spencer, Rensselaer Polytechnic Institute
3:30 PM-5:30 PM Coffee Break
Session 9: 3:50 PM-5:50 PM (Wednesday, January 30)
3:50 Circular Hulls and Orbiforms of Simple Polygons
Vijaya Chandru, Purdue University, West Lafayette, and
R. Venkataraman, Indian Institute of Science, India
4:10 Computing a Face in an Arrangement of Line Segments
Bernard Chazelle, Princeton University; Herbert Edelsbrunner,
University of Illinois, Urbana; Leonidas J. Guibas,
Massachusetts Institute of Technology; Micha Sharir, Tel Aviv
University, Israel, and Courant Institute of Mathematical
Sciences, New York University; Jack Snoeyink, Stanford
University
4:30 Planar Geometric Location Problems and Maintaining the
Width of a Planar Set
Pankaj K. Agarwal, Duke University and Micha Sharir, Tel Aviv
University, Israel, and Courant Institute of Mathematical
Sciences, New York University
4:50 The Aquarium Keeper's Problem
Jurek Czyzowicz, Universite du Quebec a Hull, Canada; Peter
Egyed and Hazel Everett, McGill University, Canada; David
Rappaport, Queen's University, Canada; Thomas Shermer, Simon
Fraser University, Canada; Diane Souvaine, Rutgers
University; Godfried Toussaint, McGill University, Canada; and Jorge
Urrutia, University of Ottawa, Canada
5:10 A Fast Algorithm for Connecting Grid Points to the
Boundary with Nonintersecting Straight Lines
Yitzhak Birk and Jeffrey B. Lotspiech, IBM Almaden
Research Center
5:30 Routing Through a Dense Channel With Minimum Total Wire Length
Michael Formann, Freie Universitat Berlin, Germany; Dorothea
Wagner, Technische Universitat Berlin, Germany; and Frank
Wagner, Freie Universitat Berlin, Germany
TRANSPORTATION INFORMATION
BY AIR
American Airlines AA has been chosen as the official carrier
for this conference. You can fly to San Francisco and save
on travel from January 22 - February 2, 1991 inclusive.
American Airlines is offering you the services of their toll
free convention reservation desk, as well as other discounts.
Get 5% off any fare for which you qualify, including
First Class and Ultra Saver fares. THE DISCOUNTS CAN
RANGE FROM 40% - 70% OFF NORMAL COACH FARES
OR... if you do not qualify for the above discounts
American Airlines will offer a minimum of 45% off regular
coach fares. Passengers whose flights originate in
Canada will be offered a 35% discount off full coach
fares. Both of these rates require a 7 day advance
purchase.
To make reservations for one of the above discounted fares:
Call American Airlines Convention Desk at 1-800-433-1790
seven days a week from 8:00 AM to 11:00 PM Eastern Time.
Be sure to mention the SIAM account number: S03Z0CN.
American Airlines will arrange to mail your tickets to
your home or office.
For those using a corporate or university travel agent,
you can still purchase your ticket through your local
agent; just be sure to mention the above discounts to
your agent. Your local agent can call the American
Airlines Convention Desk to make your reservation.
Please be sure that the agent uses the SIAM account
number: S03Z0CN
BY CAR
From the airport: Take 101 North until the freeway splits.
Go left towards the Golden Gate Bridge. Follow the Golden
Gate Bridge signs to the end of the freeway until it becomes
Franklin Street. Proceed five blocks to Post Street and turn
right. Continue to the intersection of Van Ness Avenue and
turn right. The Cathedral Hill Hotel garage entrance is in
the middle of the block on Van Ness.
>From Los Angeles: Take Highway 5 North to 580 West to the Bay
Bridge. Take the Main Street exit on the right. Proceed to
Market Street and turn left, and then take the first right
onto South Van Ness to Van Ness Street. Follow Van Ness
Street to Geary Street. The Cathedral Hill Hotel is on Van
Ness Street at Geary Street.
PUBLIC TRANSPORTATION
From the Airport: Several airport shuttle vans stop at the
platform on the arrival level of the airport. Lorries
Airport Service and the Super Shuttle depart every 20 minutes
and cost approximately $10.00. A local taxi will cost
approximately $25.00. (Prices quoted at press time.) CAR RENTAL
BUDGET-RENT-A-CAR has been selected as the official car
rental agency for this conference. The following rates will
apply between January 25 - February 2, 1991.
Type of Car Daily Rate Weekly Rate
Economy $28 $129
Intermediate $34 $169
Standard $36 $179
Reservations
We encourage you to make an advance reservation, as on-site
availability cannot be guaranteed. Make reservations by
calling 1-800-772-3773. When making reservations, be sure to
give the SIAM Rate Code:# VAR2/SODA You should also
mention that you are attending the ACM-SIAM Symposium on
Discrete Algorithms, January 28-30 in San Francisco, in order
to receive the indicated rates.
o Cars may be picked up at the San Francisco Airport at
the Budget Car Rental desk located in the baggage claim
area of the airport. You may also pick cars up at any
downtown location as well as San Jose/Oakland/Monterey airports.
o Cars must be picked up and dropped off at the same location.
o You must be 21 years of age and have a valid U.S. or
international driver's license.
o You will be given unlimited free mileage.
o You must have one of the following credit cards to rent
a car: AMEX, MasterCard, VISA, or Diners Club.
o The prices quoted do not include refueling services,
tax, optional collision damage waiver, and personal
accident insurance. HOTEL INFORMATION
Cathedral Hill Hotel
Van Ness at Geary Street
San Francisco, CA 94109
(415) 776-8200
SIAM is holding a block of rooms at the Cathedral Hill
Hotel. These rooms are being held on a first come, first
served basis at $81/Single and $97/Double. In addition,
there is an 11% occupancy tax which is added daily to the
room rate. These rooms will be held for our exclusive use
until January 6, 1991. After this date, reservations will
depend on availability.
We urge you to make your reservations as soon as possible.
You may do so by calling (415) 776-8200, or by mailing in the
Hotel Reservation Form located in the back of this program.
When making your reservation via phone, please be certain to
identify yourself as an attendee at the ACM-SIAM Symposium on
Discrete Algorithms to receive the discounted rate.
Late Arrival Policy: If you plan to check-in after 6:00 PM,
you must guarantee your room for late arrival by making
payment in advance for one night. Payment can be made by
either AMEX, MasterCard, VISA, Diners Club or check.
Check-In: Check-in time is 3:00 PM and check-out time is 1:00
PM. If you need to change or cancel your reservation, be
certain to contact the hotel by 1:00 PM Eastern Time on your
stated date of arrival to avoid any unnecessary charges.
Facilities: The Cathedral Hill is equipped with an outdoor
heated pool on the 4th floor. There is a health club 2
blocks from the hotel on Gought St., which is open to hotel
guests at a discounted rate of $10.00 per visit.
Dining: The hotel has one restaurant, the Hilltop Room, which
specializes in continental cuisine. The restaurant is open
Tuesday through Saturday from 5:30 PM to 10:30 PM. Prices
range from $14.00 to $17.00. There is also a coffee shop
that is open seven days a week from 6:00 AM to 11:00 PM. It
serves breakfast, lunch, and dinner, and the prices range
from $3.50 for breakfast to $15.00 for dinner. There are
many restaurants within walking distance of the hotel that
offer a variety of cuisines.
Parking: The Cathedral Hill Hotel offers complimentary
parking for those attendees staying at the hotel. Attendees
not staying at the hotel, however, can expect to pay an
average of $15.00 per day for parking.
Weather
Temperatures in San Francisco seldom rise above 70 or fall
below 40. A light jacket or coat or a light-to-medium weight
suit is usually adequate.
REGISTRATION INFORMATION
Please complete the Advance Registration Form found on the
back page of this brochure. We urge attendees to register in
advance, to get the lower registration fee. The advance
registration deadline is January 21, 1991. The registration
desk will be located in the Mezzanine and will be open during
the following times:
Sunday, January 27 6:00 pm-9:00 pm
Monday, January 28 7:30 am-5:30 pm
Tuesday, January 29 8:00 am-5:30 pm
Wednesday, January 30 8:00 am-3:00 pm
Registration Fees
The registration fee includes a copy of the proceedings
(available at the symposium) and three luncheons for all
regular attendees. For special meal restrictions (vegetarian
or Kosher) please be sure to check the appropriate box on
registration form.
All student attendees will receive a copy of the proceedings,
and the first 75 students to register will receive three
luncheons courtesy of SIGACT's Institutional Sponsors:
Academic Press, Inc.
Addison-Wesley Publishing Company
AT&T Bell Laboratories
Bellcore
Computer Science Press, Inc.
Digital Equipment Corporation Systems Research Center
Hewlett-Packard Laboratories
IBM Almaden Research Center
IBM Thomas J. Watson Research Center
Instituto di Analisi dei Systemi ed Informatica
John Wiley & Sons, Inc.
Morgan-Kaufmann Publishers, Inc.
Springer-Verlag New York, Inc.
Xerox Palo Alto Research Center
Advance registration deadline: January 21, 1991
Registration Fees
ACM-SIAM ACM-SIAM
Member Non-Member Student
Advance $235 $275 $50
On-Site $285 $325 $100
There will be no prorated fees. No refunds will be issued
once the symposium has started.
If SIAM does not receive your registration form and payment
on or before January 21, 1991, you will have to pay the on-
site registration fee.
SOCIAL EVENTS
Welcoming Reception
Sunday, January 27, 6:00 pm-8:00 pm
Cash Bar and mini hors d'oueuvres
Idea Exchange
Monday, January 28, 6:00 pm-7:30 pm
Mezzanine
Cost is $18--includes beer and sodas, an assortment of Asian
foods consisting of fried won tons, stir fried beef, fried
rice, eggrolls, and vegetables and dips.
CREDIT CARDS
SIAM accepts VISA, MasterCard and AMEX for payment of
registration fees and special functions. When you complete
the Advance Registration Form, please be certain to indicate
the type of credit card, the account number, and the
expiration date.
TELEPHONE MESSAGES
The telephone number at the Cathedral Hill Hotel is 1-415-
776-8200. The Cathedral Hill will either connect the caller
with the SIAM registration desk or forward a message to your
hotel room.
***************************************************************
First ACM-SIAM Symposium on
Discrete Algorithms
Hotel Reservation Form
Please send me a Confirmation
Note to attendee: Specially discounted rooms are being
held for our exclusive use until January 6, 1991. After
that date, reservations will depend on availability.
Your reservation is not confirmed until acknowledged in
writing by the hotel or verified by phone. When making
reservations by phone, be sure to identify yourself as an
attendee at the ACM-SIAM Symposium on Discrete
Algorithms. Telephone: 1-415-776-8200.
Please Print
Name______________________________________________
Phone_____________________________________________
Address___________________________________________
City______________________________________________
State_____ Zip______ Country______________________
Please Reserve: [ ] Single ($81) [ ] Double ($97)
Arrival Date_____________ Arrival Time____________
Check-out Date______________
Guarantee my room for late arrival (after 6:00 pm)
[ ] Yes [ ] No
(Requires one night's deposit by check or credit card)
I wish to pay by: [ ] AMEX [ ] VISA [ ] MasterCard
[ ] Check
Credit Card_______________________________________
Exp. Date_________________________________________
Deposit_______________________ (Late arrival only)
Signature_________________________________________
Mail this reservation form to:
Reservations
The Cathedral Hill Hotel
Van Ness at Geary Street
San Francisco, CA 94109
***************************************************************
First ACM-SIAM Symposium on
Discrete Algorithms
Advance Registration Form
Registration Fees
ACM-SIAM ACM-SIAM
Member Non-Member Student
Advance $235 $275 $50
On-Site $285 $325 $100
Symposium ______ ______ ______
Idea Exchange $18 ______ ______ ______
Total ______ ______ ______
Special Meal Request:
[ ] Vegetarian [ ] Kosher
Please Print
Name______________________________________________
Affiliation_______________________________________
Department________________________________________
Address___________________________________________
City______________________________________________
State_____ Zip______ Country______________________
Telephone_________________________________________
Local Address in San Francisco____________________
__________________________________________________
I wish to pay by: [ ] AMEX [ ] VISA [ ] MasterCard
[ ] Check (payable to SIAM)
Credit Card_______________________________________
Exp. Date_________________________________________
Signature_________________________________________
[ ] Please send information about SIAM membership
Mail this registration form and payment to:
SIAM
3600 University City Science Center
Philadelphia, PA 19104-2688
Telephone: 215-382-9800.
Advance Registration Form must be received at the SIAM
office by January 21, 1991.