Tuesday
Wednesday
Thursday
Scope
The 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2006), and the 10th International Workshop on Randomized Techniques in Computation (RANDOM 2006) will be held at UPC Barcelona, from August 28-31, 2006. APPROX 2006 focuses on algorithmic and complexity theoretic issues relevant to the development of efficient approximate solutions to computationally difficult problems, while RANDOM 2006 focuses on applications of randomness to computational and combinatorial problems. RANDOM 2006 is the tenth workshop in the series; APPROX 2006 is the ninth in the series.
Topics
Papers are solicited in all research areas related to randomization and approximation, including, but not limited to:
APPROX
* design and analysis of approximation algorithms
* hardness of approximation
* small space and data streaming algorithms
* sub-linear time algorithms
* embeddings and metric space methods
* mathematical programming methods
* coloring and partitioning
* cuts and connectivity
* game theory and applications
* geometric problems
* network design and routing
* packing and covering
* scheduling
* other applications
RANDOM
* 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
* Physics methods in Computer Science
Publication
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 and 3624 while previous proceedings of RANDOM appeared as LNCS 1269, 1518, 1671, 2129, 2483, 2764, 3122, 3624 and as Proceedings in Informatics 8.
Guidelines for Submission
Electronic submissions are solicited. To electronically submit a paper or for more specific submission instructions, please consult the conference web page:
http://cui.unige.ch/tcs/random-approx/
The postscript must be received by 17:00pm (PDT) of April 18th for your submission to be considered. Simultaneous submission to other conferences with published proceedings is not allowed.
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