[Opt-net] APPROX 2009 and RANDOM 2009 - -- deadline 12. April

Fri Apr 10 19:57:31 MEST 2009

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 at cs.technion.ac.il

RANDOM
Irit Dinur,
Weizmann Institute
email:
irit.dinur at weizmann.ac.il

Workshop Chairs

Klaus Jansen,
U. of Kiel
e-mail: kj at informatik.uni-kiel.de

José Rolim,
U. of Geneva
e-mail: rolim at cui.unige.ch

Local Chairs

Neha Dave,
UC Berkeley
e-mail: nehad at eecs.berkeley.edu

CONFERENCE WEB PAGE

http://cui.unige.ch/tcs/random-approx/