This volume contains the papers presented at the 14th International Workshop
on Approximation Algorithms for Combinatorial Optimization Problems
(APPROX 2011) and the 15th International Workshop on Randomization and
Computation (RANDOM 2011), which took place concurrently in Princeton
University, USA, during August 17–19, 2011.
APPROX focuses on algorithmic and complexity issues surrounding the development
of efficient approximate solutions to computationally difficult problems,
and was the 14th in the series after Aalborg (1998), Berkeley (1999),
Saarbr¨ucken (2000), Berkeley (2001), Rome (2002), Princeton (2003), Cambridge
(2004), Berkeley (2005), Barcelona (2006), Princeton (2007), Boston (2008),
Berkeley (2009), and Barcelona (2010). RANDOM is concerned with applications
of randomness to computational and combinatorial problems, and was the
15th workshop in the series following Bologna (1997), Barcelona (1998), Berkeley
(1999), Geneva (2000), Berkeley (2001), Harvard (2002), Princeton (2003),
Cambridge (2004), Berkeley (2005), Barcelona (2006), Princeton (2007), Boston
(2008), Berkeley (2009), and Barcelona (2010).
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, mathematical programmingmethods, combinatorial problems in graphs
and networks, game theory, markets and economic applications, geometric problems,
packing, covering, scheduling, approximate learning, design and analysis
of online algorithms, 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, and other applications of approximation and randomness.
The volume contains 29 contributed papers, selected by the APPROX Program
Committee out of 66 submissions, and 29 contributed papers, selected by
the RANDOM Program Committee out of 64 submissions.
We would like to thank all of the authors who submitted papers, the two
invited speakers, David P. Williamson and Joel Spencer, the members of the
Program Committees, and the external reviewers.
