This volume contains the papers presented at the 12th International Wo- shop on Approximation
Algorithms for Combinatorial Optimization Problems (APPROX 2009) and the 13th International
Workshop on Randomization and Computation (RANDOM 2009) which took place concurrently at the
HP - ditorium in UC Berkeley USA during August 21 23 2009. APPROX focuses on algorithmic and
complexity issues surrounding the development of e?cient approximate solutions to
computationally di?cult problems and was the 12th in the series after Aalborg (1998) Berkeley
(1999) Saarbru cken (2000) Ber- ley (2001) Rome (2002) Princeton (2003) Cambridge (2004)
Berkeley (2005) Barcelona (2006) Princeton (2007) and Boston (2008). RANDOM is concerned
with applications of randomness to computational and combinatorial problems and was the 13th
workshop in the series following Bologna (1997) Barcelona (1998) Berkeley(1999) Geneva(2000)
Berkeley(2001) Harvard(2002) Prin- ton (2003) Cambridge (2004) Berkeley (2005) Barcelona
(2006) Princeton (2007) and Boston (2008). Topics of interest for APPROX and RANDOM are:
design and analysis of approximation algorithms hardness of approximation small space
algorithms sub-linear time algorithms streaming algorithms embeddings and metric space
methods mathematicalprogrammingmethods combinatorialproblemsingraphs andnetworks gametheory
markets andeconomicapplications geometricpr- lems packing covering scheduling approximate
learning design and analysis of online algorithms randomized complexity theory
pseudorandomness and - randomization randomcombinatorialstructures randomwalks Markovchains
expander graphs and randomness extractors probabilistic proof systems err- correctingcodes
average-caseanalysis propertytesting computationallearning theory and other applications of
approximation and randomness. The volume contains 25 contributed papers selected by the APPROX
Program Committee out of 56 submissions and 28 contributed papers selected by the RANDOM
Program Committee out of 57 submissions.
