From dmanet@math.utwente.nl Sat Jul 3 20:45:17 1999 Date: Wed, 16 Jun 1999 18:01:37 +0200 From: Discrete Mathematics and Algorithms Network Reply-To: klaus@idsia.ch To: DMA-LIST@NIC.SURFNET.NL Subject: RANDOM-APPROX'99 Conference Tentative Program, Registration and Housing Information for RANDOM-APPROX'99 Conference August 9-11, 1999 Soda Hall 306 Computer Science Department University of California, Berkeley MEETING INFORMATION The meeting will be held at the Computer Science Department, University of California, Berkeley (Soda Hall) August 9-11, 1999. Registration will take place Monday, August 9 at the Soda Hall from 12:00 am. ---------------------------------------------------------------------------- TENTATIVE PROGRAM Monday - August 9th, 1999 Registration Starts at 12:00am 1:30pm : Invited Talk Christos Papadimitriou: title TBA Session: Random 1 2:20pm: Completeness and robustness properties of min-wise independent permutations Andrei Broder and Michael Mitzenmacher 2:45pm: Discrepant Sets Yield Approximate Min-Wise Independent Permutation Families Michael Saks, Aravind Srinivasan, Shiyu Zhou and David Zuckerman 3:10pm: Coffee Break Session: Approx 1 3:30pm: Independent Sets in Hypergraphs with Applications to Routing Via Fixed Paths Noga Alon, Uri Arad and Yossi Azar 3:55pm: Approximating Minimum Manhattan Networks Joachim Gudmundsson, Christos Levcopoulos and Giri Narasimhan 4:20pm: Approximation of Multi-Color Discrepancy Benjamin Doerr and Anand Srivastav 4:55pm: A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem Hans Kellerer Tuesday - August 10th, 1999 8:30am: Invited Talk Information-theoretic notions in computational complexity Madhu Sudan Session: Approx 2 9:20am: Set Cover with Requirements and Costs Evolving over Time Milena Mihail 9:45am: Multi-coloring Planar graphs and Partial k-Trees Magnus M Halldorsson and Guy Kortsarz 10:05am: Coffee Break Session: Random 2 10:25am: Testing the Diameter of Graphs Michal Parnas and Dana Ron 10:50am: Improved Testing Algorithms for Monotonicity Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron and Alex Samorodnitsky 11:15am: Linear Consistency Testing Yonatan Aumann, Michael O. Rabin and Madhu Sudan 11:40am: Improved Bounds for Sampling Contigency Tables Benjamin James Morris Lunch Break 1:30 am: Invited Talk Probabilistic and Deterministic Approximations of the Permanent Avi Wigderson Session: Random 3 2:20pm: Improved derandomization of BPP using a hitting set generator Oded Goldreich and Avi Wigderson. 2:45pm: Probablistic Construction of Small Strongly Sum-Free Sets via Large Sidon Sets Andreas Baltz, Tomasz Schoen and Anand Srivastav 3:10pm: Coffee Break Session: Approx 3 3:30pm: Stochastic Machine Scheduling: Performance Guarantees for LP-based Priority Policies Rolf H. Moehring, Andreas S. Schulz and Marc Uetz 3:55pm: Efficient Redundant Assignments under Fault-Tolerance Constraints Dimitris Fotakis and Paul Spirakis 4:20pm: Scheduling with Machine Cost Csanad Imreh and John Noga 4:55pm: A linear time approximation scheme for the job shop scheduling problem. Klaus Jansen, Roberto Solis-Oba and Maxim Sviridenko 6:30 pm: Banquet Wednesday - August 11th, 1999 11:00am-12:00am: MINISYMPOSIUM ON SCHEDULING Organizer: Klaus Jansen Speakers: Susanne Albers Evripidis Bampis Stefano Leonardi 1:30pm: Invited Talk Randomized rounding of semidefinite programs - variations on the MAX CUT example Uri Feige Session: Approx 4 2:20pm: Hardness Results for the Power Range Assignment Problem in Packet Radio Networks Andrea E. F. Clementi, Paolo Penna and Riccardo Silvestri 2:45pm: A New Approximation Algorithm for the Demand Routing and Slotting Problem with Unit Demands on Rings Christine Cheng 3:10pm: Coffee Break Session: Random 4 3:30pm: Algorithms for Graph Partitioning on the Planted Partition Model Anne E. Condon and Richard M. Karp 3:55pm: A Randomized Time-Work Optimal Parallel Algorithm for Finding a Minimum Spanning Forest Seth Pettie and Vijaya Ramachandran 4:20pm: Fast Approximate PCPs for Multidimensional Bin-packing Problems Tugkan Batu, Ronitt Rubinfeld and Patrick White 4:55am: Pfaffian Algorithms for Sampling Routings on Regions with Free Boundary Conditions Russell Martin and Dana Randall ---------------------------------------------------------------------------- REGISTRATION Please complete all information on the Registration and Housing form and return it by mail or fax before June 30, 1999. Because of current accounting procedures, we are unable to accept registration via the Web at this time. Please print the registration form and mail or fax it to the conference coordinator. You may make one payment for both registration and housing fees. The registration fee of regular or student, covers entrance to all sessions, a copy of the conference proceedings, the banquet, on Tuesday evening coffee breaks and conference costs. The early registration fee is $200 and the early student fee is $170. After June 30, regular fees of $280 and $250 for students apply. ---------------------------------------------------------------------------- HOUSING Housing for the Conference has been arranged at the Residence Hall Unit 1 of the University of California, Berkeley. The number of rooms is LIMITED and will be reserved on a first in basis. The suites have two bedrooms which share a common living area and bathroom. Each bedroom may be booked for either single or double occupancy. Each bedroom has two twin-sized beds, two desks and two chests of drawers. All rooms may be booked for either single or double occupancy. If requesting double occupancy, please indicate the name of the person with whom you wish to share (each roommate should indicate). If no choice is given a roommate will be assigned for you. Accommodations are sold as a package which includes 3 nights of housing (Sunday, Monday and Tuesday ), 3 breakfasts (Monday, Tuesday and Wednesday), 2 dinners (Sunday, Monday) and 3 lunches (Monday, Tuesday and Wednesday). Package begins with dinner on Sunday, August 8 and ends with lunch on Wednesday, August 11. No refunds can be made for late arrival or early departure. Rates are on a per person basis: $200.00 for single Occupancy and $170.00 for Double Occupancy Suite. The meals will be served at the Residence Hall Unit 1. ---------------------------------------------------------------------------- EARLY ARRIVALS Accommodations fees at the Berkeley campus are sold as the package described above. No refunds can be made for late arrival or early departure. Guests who will be arriving early the conference dates may make individual reservations at the Summer Visitor Housing, which is independent of this conference. Reservations may be made by calling their office at (510) 642 5925 or through their web site (http://www.housing.berkeley.edu) by cliking on "Conferences Services" and then on "Summer Visitor Housing". ---------------------------------------------------------------------------- HOTELS Participants may also make reservations at local hotels. Some of the hotels listed below have special rates for UC Berkeley visitors. Berkeley Marina Radisson, 200 Marina Blvd., Berkeley (510-548-7920) Claremont Resort Hotel & Tennis Club, 41 Tunnel Road, Oakland (510-843-3000) Holiday Inn-Bay Bridge, 1800 Powell Street, Emeryville (510-658-9300) Shattuck Hotel, 2086 Allston Way, Berkeley (510-845-7300) ---------------------------------------------------------------------------- TRANSPORTATION Transportation from both San Francisco International Airport and Oakland International Airport is available through local shuttle services. Advance reservations are recommended and may be made by phoning or faxing the service providers listed below. Rates given are currently in effect and may change before the conference. Bay Porter Express Phone: (415) 467-1800 Fax: (415) 467-8783 $16.00 per person each way from San Francisco Airport $16.00 per person each way from Oakland Airport Taxi Service $60.00 (average) for 1-5 persons to Berkeley/Oakland from San Francisco Airport $45.00 (average) for 1-5 persons to Berkeley/Oakland from Oakland Airport ---------------------------------------------------------------------------- WEATHER In August, the weather is usually in the low 70's Fahrenheit during the day and will drop 10oF in the evenings. Fog is common in the evening and early mornings. Comfortable clothing is suggested, and you should bring a sweater or light jacket. Walking shoes are essential. San Francisco is usually windy and about 5oF cooler than Berkeley. ---------------------------------------------------------------------------- SPECIAL NOTES Emergency medical situations can be handled at nearby hospitals. However, these services will be charged to the individual and it is recommended that foreign visitors investigate the possibility of obtaining medical insurance prior to arrival in the United States. ---------------------------------------------------------------------------- CONFERENCE COORDINATOR For information on registration, housing or logistics contact: Jose Rolim C.U.I. University of Geneva 24 rue General Dufour 1204 Geneva Switzerland email: rolim@cui.unige.ch fax: + 41 22 705 7780 ---------------------------------------------------------------------------- ---------------------------------------------------------------------------- Registration and Housing Form for Random-Approx '99 Conference EARLY REGISTRATION DEADLINE: June 30, 1999 Family Name: ____________________________ First Name: ____________________________ Organization: ____________________________ Department: ____________________________ Organization Address: ____________________________ ____________________________ City: ____________________________ State: ____________________________ Zip Code: ____________________________ Country: ____________________________ Telephone: ____________________________ Fax: ____________________________ Email Address: ____________________________ Housing Information at Residence Hall Unit 1 Male ____ Female ____ Smoker ____ I request the following at residence Hall Unit 1: Single Occupancy Suite ____ Double Occupancy Suite ____ If double occupancy suite please indicate with whom you will share: __________________________________________________________________ If sharing with a conference attendee, each person must fill out a separate form. If double occupancy is requested and no roommate is given, the conference coordinator will assign a roommate. PAYMENT INFORMATION We are unable to accept International Postal Money Orders. Please enclose check in U.S. dollars or International Money Order payable to: Random Conference and send it to Jose Rolim C.U.I. 24 rue General Dufour 1204 Geneva Switzerland We accept payment by mail or fax using either Visa, Mastercard, or American Express. Please complete the following information when using a credit card: Type of credit card: ____________________________ Credit card number: ____________________________ Expiration date: ____________________________ Print name as shown on credit card: ____________________________ Signature: ____________________________ REGISTRATION FEES (includes entrance to all sessions, the minisymposium, a copy of the proceedings, the banquet on Tuesday evening, coffee breaks and other conference costs): $200.00 Early registration received before June 30, 1999 $________________ $170.00 Student registration received before June 30, 1999 $________________ $280.00 Regular registration $________________ $250.00 Student registration received after July 15, 1998 $________________ Subtotal Registration Fees $________________ HOUSING FEES Accommodations are sold as a package which includes 3 nights of housing (Sunday,Monday and Tuesday), 3 breakfasts, 3 lunchs (Monday, Tuesday and Wednesday), and 2 dinners (Sunday, Monday). Package begins with dinner on Sunday, August 8 and ends with lunch on Wednesday, August 11. No refunds can be made for late arrival or early departure. Rates below are on a per person basis. $200.00 Single Occupancy Suite (one person per room) $________________ $170.00 Double Occupancy Suite (two people per room) $________________ Subtotal Housing $________________ TOTAL FEES PAID (registration, other fees, and housing) $________________ Please fax or mail to: Jose Rolim Random-conference 24 rue General Dufour 1204 Geneva Switzerland email: rolim@cui.unige.ch fax: + 41 22 7057780 ****************************************************** Contributions to be spread via DMANET are submitted to DMANET@math.utwente.nl Replies to a message carried on DMANET should NOT be addressed to DMANET but to the original sender. The original sender, however, is invited to prepare an update of the replies received and to communicate it via DMANET. DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET) http://www.math.utwente.nl/stor/OR/dmanet.html