Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!ucsd!ucbvax!RESEARCH.ATT.COM!dsj From: dsj@RESEARCH.ATT.COM (David Johnson) Newsgroups: comp.theory Subject: Brochure for SODA-91 (registration form at end) Message-ID: <9011261455.AA01191@irt.watson.ibm.com> Date: 26 Nov 90 14:55:25 GMT Sender: daemon@ucbvax.BERKELEY.EDU Reply-To: Theory-A - TheoryNet World-Wide Events , David Johnson Lines: 664 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.