25-27 August 2008
Cambridge MA, U.S.A.
APPROX 2008 and RANDOM 2008 11th Intl. Workshop on Approximation Algorithms for Combinatorial Optimizat ion Problems - APPROX 2008 12th Intl. Workshop on Randomization and Computation - RANDOM 2008 http://cui.unige.ch/tcs/random-approx/ 25-27 August 2008 MIT Call for papers SCOPE The 11th. International Workshop on Approximation Algorithms for Combinator ial Optimization Problems (APPROX'2008), and the 12th. International Workshop o n Randomized Techniques in Computation (RANDOM'2008) will be held at the Kiva-Patil seminar room, Building 32 (Ray and Maria Stata Center) - MIT, on August 25-27, 2008. APPROX'2008 focuses on algorithmic and complexity theoretic issues relevant to the development of efficient approximate solutions to computationally difficult problems, while RANDOM'2008 focuses on applications of randomness to computational and combinatorial problems. RANDOM'2008 is the twelfth workshop in the series; APPROX'2008 is the eleventh in the series. TOPICS Papers are solicited in all research areas related to randomization and approximation, including, but not limited to: APPROX .=09design and analysis of approximation algorithms .=09hardness of approximation .=09small space, sub-linear time, and streaming .=09algorithms .=09embeddings and metric space methods .=09mathematical programming methods .=09combinatorial problems in graphs and networks .=09game theory, markets, and economic applications .=09geometric problems .=09packing, covering, and scheduling .=09approximate learning .=09other applications RANDOM .=09design and analysis of randomized algorithms .=09randomized complexity theory .=09pseudorandomness and derandomization .=09random combinatorial structures .=09random walks/Markov chains .=09expander graphs and randomness extractors .=09probabilistic proof systems .=09random projections and embeddings .=09error-correcting codes .=09average-case analysis .=09property testing .=09computational learning theory SUBMISSIONS Abstract Format: Electronic submissions are solicited. Please consult the following servers: For submission of APPROX papers: http://www.easychair.org/APPROX2008/ For submission of RANDOM papers: http://www.easychair.org/RANDOM2008/ Note: You will be asked to login using an EasyChair account. Directions on how to register for such an account are available at the submission servers (you may also have an old account from a previous confer ence submission). The submission must be received by 17:00pm (PDT) of April 7 for it to be considered. Abstract Format: Authors should submit an extended abstract (not a full pap er). An abstract should start with the title of the paper, each author's name, affiliation, and e-mail address, followed by a one-paragraph summary of the results to be presented. This should then be followed by a technical exposition of the main ideas an d techniques used to achieve these results including motivation and a clear comparison with related work. The abstract should not exceed 10 single-spaced pages on letter-size paper, using reasonable margins and at least 11-point font. If the authors believe that more details are essential to substantiate the main claims of the pape r, they may include a clearly marked appendix that will be read at the discret ion of the program committee. Simultaneous submission Simultaneous submission to other conferences with published proceedings is not allowed. PROCEEDINGS Proceedings will be published in the Springer-Verlag series Lecture Notes i n Computer Science. Previous proceedings of APPROX appeared as LNCS 1444, 1671, 1913, 2129, 246 2, 2764, 3122, 3624, 4110 and 4627 while previous proceedings of RANDOM appear ed as LNCS 1269, 1518, 1671, 2129, 2483, 2764, 3122, 3624, 4110, 4627 and as Proceedings in Informatics 8. IMPORTANT DATES .=09Submission deadline: April 7, 2008 .=09Notification to authors: May 23, 2008 .=09Camera ready: June 15, 2008 PROGRAM COMMITTEES APPROX Matthew Andrews, Bell Labs Timothy Chan, University of Waterloo Julia Chuzhoy, Toyota Technological Institute Uriel Feige, Weizmann Institute Ashish Goel, Stanford University, (Chair) Elad Hazan, IBM Research Stefano Leonardi, Universita' di Roma "La Sapienza" Aranyak Mehta, Google Vahab Mirrokni, Microsoft Research Kamesh Munagala, Duke University Adi Rosen, CNRS & Universit Paris Sud David Shmoys, Cornell University Adrian Vetta, McGill University Jan Vondrak, Princeton University David Williamson, Cornell University RANDOM Nir Ailon, Google Research NY Tugkan Batu, London School of Economics Petra Berenbrink, Simon Fraser University Harry Buhrman, CWI and University of Amsterdam Amin Coja-Oghlan, University of Edinburgh Anna Gal, University of Texas at Austin Yuval Ishai, Technion and UCLA David Kempe, University of Southern California Adam Klivans, University of Texas at Austin Ronitt Rubinfeld, MIT (Chair) Alex Samorodnitsky, Hebrew University of Jerusalem Amir Shpilka, Technion Martin Strauss, University of Michigan Eric Vigoda, Georgia Tech David Woodruff, IBM Almaden PROGRAM CHAIRS APPROX Ashish Goel, Stanford University email: ashishg@stanford.edu RANDOM Ronitt Rubinfeld, MIT email: ronitt@csail.mit.edu WORKSHOP CHAIRS Klaus Jansen, U. of Kiel e-mail: kj@informatik.uni-kiel.de Jos Rolim, U. of Geneva e-mail: rolim@cui.unige.ch STEERING COMMITTEE APPROX Susanne Albers, U. of Freiburg Dorit Hochbaum, UC Berkeley Klaus Jansen, U. of Kiel Samir Khuller, Maryland Jos Rolim, U. of Geneva Vijay Vazirani, Georgia Tech RANDOM Josep Diaz, UPC Barcelona Oded Goldreich, Weizmann Klaus Jansen, U. of Kiel Michael Luby, Digital Fountain Christos Papadimitriou, UC Berkeley Jose Rolim, U. of Geneva Paul Spirakis, U. of Patras CONFERENCE WEB PAGE http://cui.unige.ch/tcs/random-approx/