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.

Keywords

Bibliographic Information

Book Title: Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
Book Subtitle: 11th International Workshop, APPROX 2008 and 12th International Workshop, RANDOM 2008, Boston, MA, USA, August 25-27, 2008
Editors: Ashish Goel, Klaus Jansen, José D. P. Rolim, Ronitt Rubinfeld
Series Title: Lecture Notes in Computer Science
DOI: https://doi.org/10.1007/978-3-540-85363-3
Publisher: Springer Berlin, Heidelberg
eBook Packages: Computer Science, Computer Science (R0)
Copyright Information: Springer-Verlag Berlin Heidelberg 2008
Softcover ISBN: 978-3-540-85362-6Published: 12 August 2008
eBook ISBN: 978-3-540-85363-3Published: 28 August 2008
Series ISSN: 0302-9743
Series E-ISSN: 1611-3349
Edition Number: 1
Number of Pages: XII, 604
Topics: Programming Techniques, Theory of Computation, Algorithm Analysis and Problem Complexity, Discrete Mathematics in Computer Science, Numeric Computing

Publish with us

Policies and ethics

Editors:

Sections

Buy it now

Buying options

Other ways to access

Table of contents (47 papers)

Front Matter

Contributed Talks of APPROX

Other Volumes

Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques

About this book