21-23 August 2009
Berkeley CA, U.S.A.
APPROX 2009 and RANDOM 2009 12th Intl. Workshop on Approximation Algorithms for Combinatorial Optimization Problems - APPROX 2009 13th Intl. Workshop on Randomization and Computation - RANDOM 2009 21-23 August 2009, HP Auditorium UC Berkeley, USA Call for papers SCOPE The 12th. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX'2009), and the 13th. International Workshop on Randomized Techniques in Computation (RANDOM'2009) will be held at the HP Auditorium/306 Soda Hall, UC Berkeley, on August 21-23, 2009. APPROX'2009 focuses on algorithmic and complexity theoretic issues relevant to the development of efficient approximate solutions to computationally difficult problems, while RANDOM'2009 focuses on applications of randomness to computational and combinatorial problems. RANDOM'2009 is the thirteenth workshop in the series; APPROX'2009 is the twelvth in the series. TOPICS Papers are solicited in all research areas related to randomization and approximation, including, but not limited to: APPROX * design and analysis of approximation algorithms * hardness of approximation * small space, sub-linear time, and streaming * algorithms * embeddings and metric space methods * mathematical programming methods * combinatorial problems in graphs and networks * game theory, markets, and economic applications * geometric problems * packing, covering, and scheduling * approximate learning * other applications RANDOM * design and analysis of randomized algorithms * randomized complexity theory * pseudorandomness and derandomization * random combinatorial structures * random walks/Markov chains * expander graphs and randomness extractors * probabilistic proof systems * random projections and embeddings * error-correcting codes * average-case analysis * property testing * computational learning theory SUBMISSIONS Abstract Format: Electronic submissions are solicited. Please consult the following servers: For submission of APPROX papers: http://www.easychair.org/conferences/?conf=approx2009 For submission of RANDOM papers: http://www.easychair.org/conferences/?conf=random09 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 conference submission). The postscript must be received by 17:00pm (PDT) of April 12 for your submission to be considered. Abstract Format: Authors should submit an extended abstract (not a full paper). 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 and 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 paper, they may include a clearly marked appendix that will be read at the discretion 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 in Computer Science. Previous proceedings of APPROX appeared as LNCS 1444, 1671, 1913, 2129, 2462, 2764, 3122, 3624, 4110 and 4627 while previous proceedings of RANDOM appeared as LNCS 1269, 1518, 1671, 2129, 2483, 2764, 3122, 3624, 4110, 4627 and as Proceedings in Informatics 8. IMPORTANT DATES Submission deadline April 12, 2009 Notification to authors June 1, 2009 Camera ready June 15, 2009 Conference August 21-23, 2009 PROGRAM COMMITTEES APPROX Nikhil Bansal, IBM T. J. Watson Research Center Ziv Bar-Yossef, Google Artur Czumaj, University of Warwick Michel Goemans, Massachusetts Institute of Technology Sudipto Guha, University of Pennsylvania Magnus Halldorsson, Reykjavik University Dorit Hochbaum, University of California, Berkeley Elias Koutsoupias, University of Athens Robi Krauthgamer, Weizmann Institute of Science Ravi Kumar, Yahoo! Research Lap Chi Lau, Chinese University of Hong Kong Seffi Naor, Technion, Chair Tim Roughgarden, Stanford University Bruce Shepherd, McGill University Tami Tamir, The Interdisciplinary Center RANDOM Irit Dinur (chair), Weizmann Institute Vitaly Feldman, IBM Almaden Parikshit Gopalan, Microsoft Research, Silicon Valley Danny Gutfreund, MIT Prahladh Harsha, Technion & Univ. of Texas, Austin Avinatan Hassidim, MIT Russel Impagliazzo, IAS & UCSD Mark Jerrum, Queen Mary, University of London Tali Kaufman, MIT Subhash Khot, NYU J. Radhakrishnan, Tata Institute of Fundamental Research Dana Randall, Georgia Tech Michael Saks, Rutgers University Adi Shraibman, Weizmann Institute Emanuele Viola, Northeastern University PROGRAM CHAIRS APPROX Seffi Naor, Israel Institute of Technology email: naor@cs.technion.ac.il RANDOM Irit Dinur, Weizmann Institute email: irit.dinur@weizmann.ac.il 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 Local Chairs Neha Dave, UC Berkeley e-mail: nehad@eecs.berkeley.edu CONFERENCE WEB PAGE http://cui.unige.ch/tcs/random-approx/