From - Tue Dec 2 02:10:29 1997 Received: from CS.Stanford.EDU (CS.Stanford.EDU [171.64.64.64]) by robotics.Stanford.EDU (8.8.7/8.8.7) with ESMTP id JAA24242; Tue, 18 Nov 1997 09:27:52 -0800 (PST) Received: from listserv-mail.surfnet.nl (listserv-mail.surfnet.nl [192.87.5.141]) by CS.Stanford.EDU (8.8.7/8.8.7) with ESMTP id JAA28403; Tue, 18 Nov 1997 09:28:34 -0800 (PST) Received: from listserv-mail (192.87.5.141) by listserv-mail.surfnet.nl (LSMTP for Windows NT v1.1a) with SMTP id <0.098F9610@listserv-mail.surfnet.nl>; Tue, 18 Nov 1997 18:23:15 +0100 Received: from NIC.SURFNET.NL by NIC.SURFNET.NL (LISTSERV-TCP/IP release 1.8c) with spool id 2934 for DMA-LIST@NIC.SURFNET.NL; Tue, 18 Nov 1997 18:28:48 +0100 Received: from HEARN (NJE origin SMTP@HEARN) by HEARN.NIC.SURFNET.NL (LMail V1.2c/1.8c) with BSMTP id 2732; Tue, 18 Nov 1997 18:28:48 +0100 Received: from utmfu6.math.utwente.nl by HEARN.nic.SURFnet.nl (IBM VM SMTP V2R2) with TCP; Tue, 18 Nov 97 18:28:46 +0100 Received: from utmfu0.math.utwente.nl (utmou1.math.utwente.nl) by utmfu6.math.utwente.nl with ESMTP (1.40.112.8/16.2) id AA085314045; Tue, 18 Nov 1997 18:27:26 +0100 Received: by utmfu0.math.utwente.nl ($Revision: 1.36.108.11 $/16.2) id AA065194043; Tue, 18 Nov 1997 18:27:23 +0100 Mailer: Elm [revision: 66.36.1.1] Approved-By: DMANET Message-ID: <199711181727.AA065194043@utmfu0.math.utwente.nl> Date: Tue, 18 Nov 1997 18:27:22 MET Reply-To: owner-emailnets@iyar.rutgers.edu Sender: DMANET From: DMANET Subject: DIMACS Workshop on Randomization Methods in Algorithm Design To: DMA-LIST@NIC.SURFNET.NL Status: O X-Status: -------------------------------------------------------------------------- | DIMACS: Center for Discrete Mathematics & Theoretical Computer Science | | A National Science Foundation Science and Technology Center | -------------------------------------------------------------------------- DIMACS Workshop on Randomization Methods in Algorithm Design Date: December 12 - 14, 1997 Location: Princeton University Organizers: Panos Pardalos, Univ. of Florida pardalos@ufl.edu Sanguthevar Rajasekaran, Univ. of Florida raj@cise.ufl.edu Jose Rolim, Univ. of Geneva Jose.Rolim@cui.unige.ch Randomization has played an important role in many optimization algorithms (both sequential and parallel). This workshop is a forum for bringing together researchers working in the theory and implementation aspects of algorithms involving radomization. The last decade has witnessed a tremendous growth in the area of randomized algorithms. During this period, randomized algorithms went from being a tool in computational number theory to finding widespread application in many types of algorithms. Major topics to be covered in the workshop include randomization techniques for linear and integer programming problems, randomization in the design of approximate algorithms for combinatorial problems, randomization in parallel and distributed algorithms, practical implementation of randomized algorithms, de-randomization issues, and pseudo-random generators. This workshop is organized in the context of the 1996-1998 special year on Discrete Probability. Program: Friday, December 12, 1997 08:30--09:00 Continental Breakfast (each day) 09:00--09:05 Welcome from the DIMACS Director and the Organizers 09:05--09:10 Distinguished Speaker introduced by J. Rolim 09:10--10:00 Distinguished Lecture Oded Goldreich, "Combinatorial Property Testing (a survey)" 10:00--10:15 Break Session F.A Chairman: Panos Pardalos 10:15--11:00 Vijay V. Vazirani, "Randomized Voting Lemmas for Set Cover" (joint work with S. Rajagopalan) 11:00--11:30 Eric Allender, "Making Nondeterminism Unambiguous" 11:30--12:00 Aravind Srinivasan, "Multicommodity Flow and Circuit Switching" 12:00--01:30 LUNCH Session F.B Chairman: S. Rajasekaran 01:30--02:00 Ravi Boppana, "Leader Election with Perfect Information" 02:00--02:30 Ted Theodosopoulos "Some Remarks on the Optimal Level of Randomization in Global Optimization" 02:30--03:00 Igor Pak, "Constructive recognition of a gray box group isomorphic to $S_n$ and Goldbach's Conjecture" (joint work with S. Bratus) 03:00--03:30 Break Session F.C Chairman: Jose Rolim 03:30--04:00 Yossi Matias, "Title to be announced" 04:00--04:30 Santosh Vempala, "An Approximation Algorithm for the Minimum Bandwidth of a Graph" 04:30--05:00 Lydia Kavraki, "A Randomized Approach to Robot Path Planning" (joint work with D. Hsu, J-C. Latombe, R. Motwani, and P.Raghavan) Saturday, December 13, 1997 Session Sa.A Chairman: S. Rajasekaran 08:00--08:45 Continental Breakfast 08:45--09:15 Paul Spirakis, "Cover Times in stochastic graphs" (joint work with J. Reif, M. Yung, S.Nikoletseas and C. Kaklamanis) 09:15--09:45 R. Barve, E.F. Grove and Jeff Vitter, "Practical parallel external mergesort using limited randomization" 09:45--10:15 Michel Bender, "Title to be announced" 10:15--10:30 Break Session Sa.B Chairman: S. Rajasekaran 10:30--11:00 DingZhu Du, "On average complexity of group testing algorithms" 11:00--11:30 John Franco, "Probabilistic Lower Bounds on the Complexity of Some Algorithms for Satisfiability" 11:30--12:00 George Havas "Randomized algorithms for multiple gcd calculation" (joint work with Gene Cooperman and Joachim von zur Gathen) 12:00--01:30 LUNCH Session Sa.C Chairman: Panos Pardalos 01:30--02:00 R. Battiti , Alan Bertossi , Romeo Rizzi, "Randomized and Reactive Algorithms for the Graph Partitioning Problem" 02:00--02:30 P.M.Pardalos and M.G.C. Resende, "A Greedy Randomized Adaptive Search Procedure for the Steiner Problem in Graphs" 02:30--03:00 Jonas Mockus, Audris Mockus, and Linas Mockus, "Bayesian Approach for Randomization of Heuristic Algorithms of Discrete Programming" 03:00--03:30 Break Session Sa.D Chairman: Jose Rolim 03:30--04:00 Sanguthevar Rajasekaran, "Computing on Optical Models" 04:00--04:30 Bill Steiger, "On the Mixing rate of the Triangulation Walk" (joint work with Mike Molloy and Bruce Reed) 04:30--05:00 Eric Baum, "On genetic algorithms" Sunday, December 14, 1997 Session Su.A Chairman: Jose Rolim 08:00--08:45 Continental Breakfast 08:45--09:15 Ravi Kannan "Low-Rank Approximations to Matrices" 09:15--09:45 David Zuckerman, "Weak random sources, random sampling, and $BPP \subseteq PH$" 09:45--10:15 Luca Trevisan, "The Approximability of Non-Boolean Constraint Satisfaction Problem" (joint work with Maria Serna and Fatos Xhafa) 10:15--10:30 Break Session Su.B Chairman: Jose Rolim 10:30--11:00 Prasad Tetali, "Title to be announced" 11:00--11:30 Andrei Broder, "Min-Wise Independent Permutations" 11:30--12:00 Klaus Jansen, "An approximation scheme for bin packing with conflicts" 12:00--01:30 LUNCH Session Su.C Chairman: Panos Pardalos 01:30--02:00 Howard Karloff, "A 7/8-Approximation Algorithm for MAX 3SAT?" 02:00--02:30 Ted Theodosopoulos "Some Remarks on the Optimal Level of Randomization in Global Optimization" 02:30--03:00 Maria Serna "Sequential and Parallel Heuristics for the MinLA Problem" DIMACS Center; Rutgers, The State University of New Jersey; 96 Frelinghuysen Road; Piscataway, NJ 08854-8018 TEL: 732-445-5928 FAX: 732-445-5932 ** EMAIL: center@dimacs.rutgers.edu WWW: http://dimacs.rutgers.edu DIMACS is a partnership of Rutgers University, Princeton University, AT&T Labs - Research, Bellcore, and Bell Laboratories. -- ****************************************************** 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)