Ashish Goel - Böcker

This volume contains the papers presented at the 11th International Wo- shop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2008) and the 12th International Workshop on Randomization and Computation (RANDOM 2008), which took place concurrently at the MIT (M- sachusetts Institute of Technology) in Boston, USA, during August 25–27, 2008. APPROX focuses on algorithmic and complexity issues surrounding the development of e?cient approximate solutions to computationally di?cult problems, and was the 11th in the series after Aalborg (1998), Berkeley (1999), Saarbru ¨cken (2000), Berkeley (2001), Rome (2002), Princeton (2003), Cambridge (2004), Berkeley (2005), Barcelona (2006), and Princeton (2007). RANDOM is concerned with applications of randomness to computational and combinatorial problems, and was the 12th 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), and Princeton (2007). Topics of interest for APPROX and RANDOM are: design and analysis of - proximation algorithms, hardness of approximation, small space, sub-linear time, streaming, algorithms, embeddings and metric space methods, mathematical programming methods, combinatorial problems in graphs and networks, game t- ory, markets, economic applications, geometric problems, packing, covering, scheduling, approximate learning, 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 - beddings, error-correcting codes,average-case analysis, property testing, com- tational learning theory, and other applications of approximation and randomness.

The 14th international meeting on DNA computation took place in the Czech Republic in Prague, June 2-9, 2008. During the last 14 years the DNA C- puting meetings have been the key forum at the boundary between computer science, biochemistry and nanotechnology where the most recent results have been presented and their authors have met. Their scienti?c program includes mathematical foundations and theoretical study of DNA computing - or b- computing in general- and recent experimental results in DNA nanotechnology, nanoscience and nanocomputing. It continues to be one of the most exciting interdisciplinary meetings, as exempli?ed by the diverse nature of contributions in this volume. The meeting began with tutorial talks by Friedrich Simmel ("Molecular - ology for Computer Scientists"), Nadrian Seeman ("Structural DNA Nanote- nology"), and Yasubumi Sakakibara ("Formal Grammars for DNA Compu- tion and Bioinformatics"). During the meeting, a number of excellent keynote speakers gave an up-to-date overview of di?erent aspects of DNA computing and biochemical information processing.Luca Cardelli talked about "Molecules as Automata," while Niles Pierce gave an exciting talk entitled "Molecular Choreography-ProgrammingNucleicAcidSelf-AssemblyandDisassemblyPa- ways."Inamorebiologicaltalk,LauraLandweberdiscussed"RNA-Guided,E- geneticProgrammingandRe-programmingofGenomicInformationinCiliates," and Ming Li gave an overview of "Modern Homology Search." The meeting was concluded by a Nanoday with beautiful presentations by Christof Niemeyer, Kurt Gothelf, Andrew Ellington and David Pine.