Monday, February 13, 2012



APPROX 2012 and RANDOM 2012

15th Intl. Workshop on Approximation Algorithms for Combinatorial
Optimization Problems - APPROX 2012
16th Intl. Workshop on Randomization and Computation - RANDOM 2012

Aug. 15-17, 2012


Call for papers


15th Intl. Workshop on Approximation Algorithms for Combinatorial
Optimization Problems - APPROX 2012

16th Intl. Workshop on Randomization and Computation - RANDOM 2012

The 15th. International Workshop on Approximation Algorithms for
Combinatorial Optimization Problems (APPROX'2012) and the 16th.
International Workshop on Randomization and Computation (RANDOM'2012) will
be held on 15-17 August 2012 at M.I.T.
APPROX'2012 focuses on algorithmic and complexity theoretic issues relevant
to the development of efficient approximate solutions to computationally
difficult problems, while RANDOM'2012 focus on applications of randomness to
computational and combinatorial problems. RANDOM'2012 is the sixteenth
workshop in the series; APPROX'2012 is the fifteenth in the series.


Papers are solicited in all research areas related to randomization and
approximation, including, but not limited to:


design and analysis of approximation
hardness of approximation
small space, sub-linear time, and
streaming algorithms
embeddings and metric space methods
mathematical programming methods
combinatorial problems in graphs and
game theory, markets, and economic
geometric problems
packing, covering, and scheduling
approximate learning
other applications


design and analysis of randomized
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 must be received by 17:00pm (EDT) of April 20 at:
in order 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 (not including the
references). 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 to other conferences with published proceedings is
not allowed.


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.


Submissions: April 20, 2012
Notifications: June 8, 2012
Camera ready: June 18, 2012



Alexandr Andoni (Microsoft Research SVC)
Yossi Azar (Tel-Aviv University)
Shuchi Chawla (University of Wisconsin - Madison)
Anupam Gupta (Carnegie Mellon University, chair)
Sariel Har-Peled (University of Illinois at Urbana-Champaign)
Jochen Koenemann (University of Waterloo)
Amit Kumar (Indian Institute of Technology, Delhi)
Lap Chi Lau (The Chinese University of Hong Kong)
Konstantin Makarychev (IBM Watson)
Monaldo Mastrolilli (IDSIA)
Dana Moshkovitz (MIT)
Rene Sitters (Vrije Universiteit Amsterdam)
David Steurer (Microsoft Research and Cornell)
Kunal Talwar (Microsoft Research SVC)
Jan Vondrak (IBM Almaden)
Lisa Zhang (Alcatel-Lucent Bell Labs)


Eli Ben-Sasson (Technion)
Andrej Bogdanov (Chinese University of Hong Kong)
Mark Braverman (Princeton)
Colin Cooper (King's College, London)
Tobias Friedrich (Saarland University / Max-Planck-Institut)
Tali Kaufman (Bar-Ilan University / Weizmann Institute of Science)
Raghu Meka (Institute for Advanced Study)
Jelani Nelson (Princeton)
Ilan Newman (University of Haifa)
Ryan O'Donnell (Carnegie Mellon University)
Konstantinos Panagiotou (Max-Planck-Institut)
Prasad Raghavendra (Georgia Tech)
Atri Rudra (University at Buffalo, SUNY)
Rocco Servedio (Columbia, chair)
Alistair Sinclair (UC Berkeley)
Emanuele Viola (Northeastern)


Anupam Gupta, Carnegie Mellon University

Rocco Servedio, Columbia University


Jose Rolim, U. of Geneva
Klaus Jansen, U. of Kiel